Vol. 48, No. 9,
Sep. 2021
Digital Library
Improving Subgraph Isomorphism with Pruning by Bipartite Matching
http://doi.org/10.5626/JOK.2021.48.9.973
In recent years, it has become increasingly important to efficiently solve NP-hard graph problems. One of the fundamental problems in graph analysis is subgraph isomorphism. Given a query graph and a data graph, the subgraph isomorphism problem is to determine whether there is an embedding of the query graph in the data graph. Although a lot of practical algorithms have been developed for the problem, existing algorithms showed limited running time scalability in dealing with many real-world graphs. In this paper, we propose a new pruning technique based on bipartite matching which enables us to capture and remove redundancies in the search space. We also conduct experiments on several real datasets to show effectiveness of our technique.
L2LRU: Learning-based Page Movement Policy for LRU Page Replacement Policy
http://doi.org/10.5626/JOK.2021.48.9.981
The LRU (least-recently used) page replacement policy has been designed to enhance the cache hit ratio by moving the page that is repeatedly accessed on the cache, to the head of the list. However, the LRU policy sometimes incurs a situation of system stall (or wait) because it requires lock-unlock commands to move each page. In this paper, we propose a new page replacement policy, called L2LRU(Learning-based Lock-free LRU), that determines whether to move or not a page by learning the reuse distance of the page with deep-learning techniques. Unlike LRU, L2LRU moves the page to the position with a high possibility of access in the near future. For evaluation, we implemented L2LRU based on trace-driven simulation and used Microsoft Research Cambridge Trace as the input of the simulation. The results clearly confirmed that L2LRU reduced the number of lock-unlock commands by up to 91% compared to the traditional LRU policy.
Defect Detection of Bridge based on Impact-Echo Signals and Long Short-Term Memory
Byoung-Doo Oh, Hyung Choi, Young Jin Kim, Won Jong Chin, Yu-Seop Kim
http://doi.org/10.5626/JOK.2021.48.9.988
PSC box girder bridges comprise various elements, of which the tendon is the most important. The tendon is exceedingly vulnerable to defects such as corrosion. So, to protect it, it is inserted into the duct and then poured concrete. However, because the inner diameter of the duct is exceedingly narrow, there is a high probability that a cavity can occur with even a minor mistake. Thus, defects are identified through the professional interpretation of signals obtained using non-destructive testing. However, this requires high cost and much time. Additionally, it is difficult to accurately identify the internal state of the concrete structure. Thus, this study intends to apply Long Short-Term Memory. In this case, the Impact-Echo method, which is often used for concrete structures, is used as an input feature. And the characteristics of the structure (concrete thickness, depth of duct, distance between the hitting point and the measuring point) are used for learning. And, the frequency component of the IE signals is additionally used. As a result, the proposed model in this study can confirm approximately 88.56% accuracy.
SMT-based Formal Verification Methods of Deep Neural Networks using Structural Properties
http://doi.org/10.5626/JOK.2021.48.9.998
Deep neural networks (DNN) are widely used for software in various fields, such as speech recognition and image classification. However, unexpected errors, such as adversarial examples, may exist in DNNs. DNN formal verification techniques to verify the requirements of DNNs are being widely studied in order to prevent these errors. This paper proposes a methodology that utilizes the structural properties of DNNs to increase the performance of DNN verification. This paper mathematically defines the structural property of DNN, suggests two structural properties of DNN with ReLU as an activation function, and shows that the verification speed of SMT-based DNN verification can be increased using the structural properties.
Interpolation Method for CT Image Reconstruction using Features Inferred by Self-Supervised Learning
http://doi.org/10.5626/JOK.2021.48.9.1007
Since volumetric data includes internal information, it has an advantage of performing quantitative analysis. Especially medical image data render 3D structures of internal organs, and cubic voxel is necessary for accurate visualization. However, CT image volume is acquired in low z-resolution to reduce X-ray dose exposure. Between slices, image interpolation is a necessary step for visualization as well as for 3D data analysis. In this paper, we propose a self-supervised learning algorithm as an interpolation method that uses the information from the high-resolution images to infer missing information between slices. To achieve this, downscaled slice images are given as the input of the network, and the network recovers the original slice images from the downscaled images. The result of our method outperformed the commonly practiced interpolation methods - nearest-neighbor and trilinear interpolation – in the field, with respect to estimating details. Also, we verified that the proposed algorithm performs comparably with the supervised model with the same network.
A Security Requirements Recommendation Framework Based on APT Attack Cases
MinJu Kim, Sihn-Hye Park, Seok-Won Lee
http://doi.org/10.5626/JOK.2021.48.9.1014
Advanced Persistent Threat (APT) attacks are intelligent and continuous attacks on specific targets. This type of attack is one of the most difficult attacks to detect and defend because it uses an organized and advanced technique for attacking targets, and it continuously attempts to attack the undetected for a certain period. In this paper, we propose a framework that recommends security requirements for real-world APT attacks as a proactive defense against APT attacks. The proposed framework derives attack elements based on scenarios for specific APT attacks and analyzes the relationships between elements. Through case-based reasoning of analytical results, attack patterns are deduced, and security requirements are recommended. For case-based reasoning and security requirements recommendation, we build an integrated knowledge base that includes APT attack knowledge, general security knowledge, and domain-specific knowledge. The integrated knowledge base consists of knowledge-specific ontology and related databases. We implement this framework as a web application to conduct case studies on specific APT attacks.
Improving Low Resource Chest X-ray Classification Accuracy by Combining Data Augmentation and Weakly Supervised Learning
http://doi.org/10.5626/JOK.2021.48.9.1027
Deep learning-based medical image analysis technology has been developed to the extent that it shows an accuracy surpassing the ability of a human radiologist. However, labeling sample data for use in learning medical images requires human experts and a great deal of time and expense. In addition, the training data for medical images has an unbalanced data distribution in many cases. For example, in the case of the ChestX-ray14 dataset, the difference between the number of data for infiltration and hernia is about 87 times. In this study, we proposed a method that combines the data augmentation algorithm Mixup and weakly supervised learning to improve the performance of data-imbalanced chest X-ray classification. The proposed method is to apply Mixup algorithm to a small number of labeled data and a large number of unlabeled data to alleviate data imbalance and performs curriculum learning that effectively utilizes the unlabeled data while cycling through the teacher model and the student model. Experimental results in an environment with a small number of labeled data and a large number of unlabeled data that can be considered in the medical field showed that the classification performance was improved by combining data augmentation and weakly supervised learning and that the cyclic curriculum learning was effective.
Ensemble Model for Detecting Abnormal Symptoms of IT Infrastructure using Time Series Access Log Data
http://doi.org/10.5626/JOK.2021.48.9.1035
When operating large-scale IT services, multiple systems need to be managed for the detection of abnormalities. Since the monitoring and control personnel can hardly have all the domain knowledge required for these systems and services, there have been increasing needs for automated models that detect abnormalities by analyzing the characteristics of each service and learning patterns. In this experiment, we use the time-series data in the access log of the web server to examine the capability of the existing spectrum residual method model in detecting the anomalies in real-time, and propose an improved detection model which can respond more quickly to an abnormal situation. Our experiment showed that the proposed model was able to predict abnormal symptoms before actual failure occurs, and to respond in advance.
A Source-code Similarity-based Automatic Tutoring Method for Online Coding Test Service
Hyunsu Mun, Soohyun Kim, Jihye Kim, Youngseok Lee
http://doi.org/10.5626/JOK.2021.48.9.1044
Recently, as IT companies have used online coding test judge systems to evaluate the abilities of developers, IT job seekers and students have been practicing coding tests. However, when a user has difficulty solving a problem, it is difficult to find a suitable hint because the coding test problem has many answers. To address this problem, this study suggested a method to find the appropriate data type to use as a hint for the user. This method measures the distance between the source codes submitted by each user and the answer source code based on the data type to find the closest one. As a result of analyzing 29,592 source code data collected from five university programming courses, the average accuracy was 85.33%, and there was a difference of about 7%, depending upon the level of the students, indicating that the proposed method was useful. This study contributes to the automatic tutoring method based on the source code submitted by the user rather than a guide prepared in advance.
An Efficient Document Clustering Method using Space Transformation based on LDA and WMD
http://doi.org/10.5626/JOK.2021.48.9.1052
The existing TF-IDF-based document clustering methods do not properly exploit the contextual information of documents, i.e., co-occurence and word-order, and tend to degrade the performance due to the curse of dimensionality. To overcome these problems, the techniques such as a weighted average of word embedding vectors or Word Mover"s Distance (WMD) have been proposed. The performance of the techniques is good at document classification, but not a document clustering that needs to group documents. In this study, we define a document group as a topic document using LDA, the document group"s representative document, and solve the existing problem by calculating the WMD based on the topic document. However, since WMD requires a large amount of computation, we propose a space transformation method that shows a good performance while reducing the computation cost by mapping each document to a low-dimensional space in which each axis means WMD value from each topic document.
UHF RFID Tag Identification Method Based on Physical-layer Features of Backscatter Networks
Yoonseo Kim, Hoorin Park, Minwoo Joo, Wonjun Lee
http://doi.org/10.5626/JOK.2021.48.9.1061
Radio-frequency identification (RFID) systems are becoming essential components in Internet of Things (IoT) networks by virtue of their cost and energy efficiency. Especially, in ultra high frequency (UHF) RFID systems, the process of identifying individual tags is crucial because different tags communicate in a passive manner. However, the tag identifiers used in existing systems are vulnerable to be replicated or predicted due to limited tag operation resources and memory, which leads to severe security threats. In this paper, we propose a technology to extract the unique physical-layer characteristics, which are difficult to be forged, and utilize them for tag identification. The proposed method consists of a fingerprint extraction algorithm to obtain the physical-layer features of time interval error and phase by analyzing the backscatter signals of the tags, and a tag identification algorithm to distinguish tags based on their extracted fingerprints. We provide a model of backscatter signals and analyze the identification accuracy of the proposed method with varying signal-to-noise ratios.
Search
Journal of KIISE
- ISSN : 2383-630X(Print)
- ISSN : 2383-6296(Electronic)
- KCI Accredited Journal
Editorial Office
- Tel. +82-2-588-9240
- Fax. +82-2-521-1352
- E-mail. chwoo@kiise.or.kr