Earticle

게임은 점차 복잡해짐에 따라 게임 환경(맵)도 복잡해지고 있다. 게임 환경(맵)이 복잡해지면 게임 신뢰성을 입증하기 위해서 많은 테스트 프로세스와 방법이 복잡해지는 경향이 있다. 본 논문에서는 자동 생성되는 게임 환경(맵)을 정확하게 진행하는지를 검증하고, 테스트를 줄일 수 있는 테스팅 기법을 AND/OR 그래프와 불식(boolen expression)을 이용하여 제안한다.

As games become ever more complex, game environments (map) are becoming increasingly complex. In this paper, I propose a method to verify the validity of the progression of the automatic map generation as it is being processed. The method It also is proposed to simplify and shorten verification test process using AND/OR graph and Boolean expressions.

다양한 스마트 기기 및 컴퓨팅 디바이스의 보급에 따라 빅데이터 생성이 광범위하게 일어나고 있다. 기계학습 은 데이터의 패턴을 학습하여 추론을 수행하는 알고리즘이다. 다양한 기계학습 알고리즘 중에서 주목을 받는 알고리 즘은 신경망 기반의 딥러닝 학습이다. 딥러닝은 다양한 응용이 발표되면서 빠른 성능 향상을 달성하고 있다. 최근 딥 러닝 알고리즘 중에서 그래프 구조를 활용하여 데이터를 분석하려는 시도가 증가하고 있다. 본 연구에서는 그래프 구 조를 활용하여 딥러닝 네트워크에 전달하기 위한 그래프 생성 방법을 제시한다. 본 논문은 그래프 생성 과정에서 노 드의 속성과 간선의 가중치를 일반화하고 행렬화 과정을 제시하여 딥러닝 입력에 필요한 구조로 전환하는 방법을 제 시한다. 그래프 생성 과정에서 속성과 가중치 정보를 보전할 수 있는 선형변환 매트릭스 적용 방법을 제시한다. 마지 막으로 일반 그래프의 딥러닝 입력 구조를 제시하고 성능 분석을 위한 접근법을 제시한다.

With the spread of various smart devices and computing devices, big data generation is occurring widely. Machine learning is an algorithm that performs reasoning by learning data patterns. Among the various machine learning algorithms, the algorithm that attracts attention is deep learning based on neural networks. Deep learning is achieving rapid performance improvement with the release of various applications. Recently, among deep learning algorithms, attempts to analyze data using graph structures are increasing. In this study, we present a graph generation method for transferring to a deep learning network. This paper proposes a method of generalizing node properties and edge weights in the graph generation process and converting them into a structure for deep learning input by presenting a matricization We present a method of applying a linear transformation matrix that can preserve attribute and weight information in the graph generation process. Finally, we present a deep learning input structure of a general graph and present an approach for performance analysis.

This paper presents an analytical technique for reliability evaluation of electrical distribution network (EDN) containing distributed generation (DG). Based on hierarchical levels of circuit breaker controlling zones and feeder sections, a directed-relation-graph (DRG) for an END is formed to describe the hierarchical structure of the EDN. The reliability indices of EDN and load points can be evaluated directly using the formed DRG, and the reliability evaluation of an EDN containing DGs can also be done without re-forming the DRG. The proposed technique incorporates multi-state models of photovoltaic and diesel generations, as well as weather factors. The IEEE-RBTS Bus 6 EDN is used to validate the proposed technique; and a practical campus EDN containing DG was also analyzed using the proposed technique.

In this paper, we report the development of two DEM (digital elevation model) generation algorithms over urban areas from an IKONOS stereo pair. One ("EpiMatch") is originally developed for SPOT images and modified for IKONOS images. It uses epipolar geometry for accurate DEM generation. The other is based on graph-cut algorithm in 3D voxel space. This algorithm is believed to work better on height discontinuities than EpiMatch. An IKONOS image pair over Taejon city area was used for tests. Using ground control points obtained from differential GPS, camera model was set up and stereo matching applied. As a result, two DEMs over urban areas were produced. Within a DEM from EpiMatch small houses appear as small "cloudy" patches and large apartment and industrial buildings are visually identifiable. Within the DEM from graph-cut we could achieve better height information on building boundaries. The results show that both algorithms can generate DEMs from IKONOS images although more research is required on handling height discontinuities (for "EpiMatch") and on faster computation (for "Graph-cut").

In this paper, we propose a new scheme for geometry coding of three-dimensional (3-D) mesh models using a fixed spectral basis. In order to code the mesh geometry information, we generate a fixed spectral basis using the dual graph derived from the 3-D mesh topology. After we partition a 3-D mesh model into several independent sub-meshes to reduce coding complexity, the mesh geometry information is projected onto the generated orthonormal bases which are the eigenvectors of the Laplacian matrix of the 3-D mesh. Finally, spectral coefficients are coded by a quantizer and a variable length coder. The proposed scheme can not only overcome difficulty of generating a fixed spectral basis, but also reduce coding complexity. Moreover, we can provide an efficient multi-resolution representation of 3-D meshes.

One of the most widely studied protocols for tactical ad-hoc networks is Optimized Link State Routing Protocol (OLSR). As for OLSR research, most research work focus on reducing control traffic overhead and choosing relay point. In addition, because OLSR is mostly dependent on link detection and propagation, dynamic Hello timer become research challenges. However, different timer interval causes imbalance of link validity time by affecting link lifetime. To solve this problem, we propose a weighted topology graph model for constructing a robust network topology based on the link validity time. In order to calculate the link validity time, we use control message timer, which is set for each node. The simulation results show that the proposed mechanism is able to achieve high end-to-end reliability and low end-to-end delay in small networks.

본 논문에서는 형태소 그래프를 정의하고 이를 한국어 연속 음성 인식의 결과로서 사용함과 동시에 한국어의 자연어 처리를 위한 지식 표현 방법으로 사용한다. 또한 형태소 그래프를 연속 음성 인식과정에서 효율적으로 생성하는 알고리즘으로서 Tree-Trellis 탐색 알고리즘을 소개한다. 한국어 연속 음성 인식기는 HMM 인식기를 사용하며 탐색 알고리즘 또한 HMM 음소 인식기의 사용을 전제로 한다. 실험 DB로는 한국과학기술원 통신연구실에서 제작한 3000 단어급의 무역상담관련 DB를 사용하였다.

시간 제약 조건을 가진 타임드 페트리넷으로부터 최적화된 비동기식 제어회로를 생성하기 위해서는 시간 분석을 통하여 도달 가능한 상태만으로 구성된 축소 상태 그래프를 생성하는 작업이 매우 중요하다. 본 논문에서는 기존의 방법들이 적용 가능한 타임드 페트리넷의 범주에 제약을 가하거나 혹은 회로의 합성과는 직접적인 상관없이 시간 분석을 위하여 대규모의 시간 상태 그래프를 부가적으로 생성하는 문제를 해결하기 위하여 타임드 페트리넷으로부터 축소된 시간 상태 그래프를 직접적으로 생성하는 방법을 제안 한다 실험 결과는 제안된 방법이 모든 범주의 타임드 페트리넷으로부터 빠른 시간 내에 합성에 충분한 축소된 상태그래프를 생성함을 보여준다.

장면 그래프는 영상 내 물체들과 각 물체 간의 관계를 나타내는 지식 그래프를 의미한다. 본 논문에서는 3차원 실내 환경을 위한 3차원 장면 그래프를 생성하는 모델을 제안한다. 3차원 장면 그래프는 물체들의 종류와 위치, 그리고 속성들뿐만 아니라, 물체들 간의 3차원 공간 관계들도 포함한다. 따라서 3차원 장면 그래프는 에이전트가 활동할 실내 환경을 묘사하는 하나의 사전 지식 베이스로 볼 수 있다. 이러한 3차원 장면 그래프는 영상 기반의 질문과 응답, 서비스 로봇 등과 같은 다양한 분야에서 유용하게 활용될 수 있다. 본 논문에서 제안하는 3차원 장면 그래프 생성 모델은 크게 물체 탐지 네트워크(ObjNet), 속성 예측 네트워크(AttNet), 변환 네트워크(TransNet), 관계 예측 네트워크(RelNet) 등 총 4가지 부분 네트워크들로 구성된다. AI2-THOR가 제공하는 3차원 실내 가상환경들을 이용한 다양한 실험들을 통해, 본 논문에서 제안한 모델의 높은 성능을 확인할 수 있었다.

Scene graph is a kind of knowledge graph that represents both objects and their relationships found in a image. This paper proposes a 3D scene graph generation model for three-dimensional indoor environments. An 3D scene graph includes not only object types, their positions and attributes, but also three-dimensional spatial relationships between them, An 3D scene graph can be viewed as a prior knowledge base describing the given environment within that the agent will be deployed later. Therefore, 3D scene graphs can be used in many useful applications, such as visual question answering (VQA) and service robots. This proposed 3D scene graph generation model consists of four sub-networks: object detection network (ObjNet), attribute prediction network (AttNet), transfer network (TransNet), relationship prediction network (RelNet). Conducting several experiments with 3D simulated indoor environments provided by AI2-THOR, we confirmed that the proposed model shows high performance.

프로그램 자동 분석 방법 중 하나인 기호 실행은 지난 몇 해 동안 기술적으로 크게 향상 되었다. 그러나 여전히 기호실행 그 자체만을 이용하여 프로그램을 분석하는 것은 실용적이지 않다. 가장 큰 이유로는 프로그램 분석 중에 발생하는 경로 폭발 문제로 인한 메모리 부족으로, 기호 실행을 이용해 프로그램의 모든 경로의 해를 구할 수 없다. 따라서 분석가는 모든 경로의 해를 구하는 것이 아닌 취약성을 갖는 지점으로 기호 실행 탐색 경로를 구성하는 것이 실용적이다. 본 논문에서는 기호 실행 과정에서 사용될 수 있는 정적분석 기반 바이너리 역방향 제어 흐름 그래프 생성 방법 기술을 제안한다. 역방향 제어 흐름 그래프 생성을 통해 분석가는 바이너리 내의 잠재적인 취약지점을 선정할 수 있고, 해당 지점으로부터 생성된 역추적 경로는 향후 기호 실행을 위해 효율적으로 사용될 수 있다. 우리는 리눅스 바이너리(x86)를 대상으로 실험을 진행하였고, 실제로 잠재적인 취약점 선정 및 역추적 경로 생성이 바이너리의 다양한 상황에서 가능함을 보였다.

Symbolic execution, an automatic search method for vulnerability verification, has been technically improved over the last few years. However, it is still not practical to analyze the program using only the symbolic execution itself. One of the biggest reasons is that because of the path explosion problem that occurs during program analysis, there is not enough memory, and you can not find the solution of all paths in the program using symbolic execution. Thus, it is practical for the analyst to construct a path for symbolic execution to a target with vulnerability rather than solving all paths. In this paper, we propose a static analysis - based backward CFG(Control Flow Graph) generation technique that can be used in symbolic execution for program analysis. With the creation of a backward CFG, an analyst can select potential vulnerable points, and the backward path generated from that point can be used for future symbolic execution. We conducted experiments with Linux binaries(x86), and indeed showed that potential vulnerability selection and backward CFG path generation were possible in a variety of binary situations.

현재의 모델 체커는 모델이 속성을 만족하지 않을 경우 반례를 사용자에게 보여주어서 디버깅을 돕는다. 모델 체커에서 반례는 중요한 장점 중에 하나이지만 대부분의 모델 체커에서 반례로서 하나의 경로만을 보여주게 된다. 하지만 사용자가 원하는 것은 그 이상의 정보를 원할 수 있다. 따라서 반례에서 좀더 많은 정보를 보여줄 필요가 있다. 이런 종류의 연구로서 트리 형식의 반례 생성과 증명 형식의 반례생성이 있었다. 하지만 이 연구들은 시스템이 가질 수 있는 모든 경로를 알아낼 수는 없고 또한 증명 형식의 반례 생성의 경우 상태공간을 다른 형식으로 변경을 해야 한다. 본 논문에서는 반례로서 도달 가능한 모든 경로를 그래프 형식으로 보여줄 수 있는 그래프 형식의 반례를 정의하고 생성방법에 대해서 알아본다

최근 BIM은 단순 3차원 모델링을 넘어 표준화된 속성 데이터의 품질 확보와 체계적 관리가 핵심 요구로 부각되고 있으며, 온톨로지 및 지식그래프 기반의 데이터 관리·추론 방식이 주목받고 있다. 그러나 지식그래프 기반 BIM 데이터는 부재 간 구조 관계 분석, 설계 검토, 물량·속성 정보 조회 등 실무 의사결정을 지원할 수 있으나, SPARQL·Cypher와 같은 그래프 질의어를 직접 작성해야 한다는 점에서 실무 적용에 제약으로 작용한다. 이를 위해 본 연구에서는 사용자가 자연어 질문을 기반으로 그래프 질의를 자동 생성할 수 있는 GraphRAG 기반 질의 자동 생성 프레임워크를 제안하였다. 먼저 CSV 기반 속성/관계 테이블에 규칙을 적용해 노드·관계를 생성하고 그래프 데이터베이스에 적재하는 CSV-to-LPG 파이프라인을 구현하여, LPG 지식그래프 구축 절차를 자동화하였다. 이후 Few-shot Learning 기반 프롬프트 설계를 통해 사용자의 자연어 질문을 Cypher 쿼리로 자동 변환하는 자동 질의 생성 모듈을 구현하였다. 전체 프레임워크는 Graph-ACQ 시스템으로 개발하여 라멘교 BIM 데이터를 기반으로 적용하였다. 검증 결과 LPG 스키마 유효성과 Cypher 자동 생성, Cypher 질의 수작업 과정에서 정확도 모두 100%를 달성하였고, 질의 생성 시간은 평균 7.1초에 처리되었다. GraphRAG 기반 질의 생성 방식은 부재 간 공간·구조 관계를 명시적으로 활용하므로, 설계·검토 과정에서 요구되는 연결 관계 분석, 구조 구성 파악, 물량·속성 정보 조회 등 관계 기반 질의를 자연어로 수행할 수 있다. 또한 Few-shot Learning 기반 접근을 적용하여 교량 뿐만 아니라 다양한 공종 내에서도 질의 생성을 가능하게 함으로써, 프로젝트의 확장성을 확보 가능하다.

Recently, Building Information Modeling (BIM) has evolved beyond three-dimensional modeling, increasingly focusing on the quality of standardized attribute data and systematic data management. Accordingly, ontology- and knowledge-graph-based data representation and reasoning approaches have increasingly gained attention. Knowledge-graph-based BIM data can support practical tasks such as structural relationship analysis, design review, and quantity and attribute information retrieval. However, practical adoption is limited by the need to manually write graph query languages, such as SPARQL and Cypher, which requires detailed knowledge of graph schemas and query syntax. To address this limitation, a GraphRAG-based automated query generation framework that converts natural-language questions into graph queries is proposed. A CSV-to-Labeled Property Graph (LPG) pipeline is developed to automate graph construction by generating nodes and relationships from rule-based attribute and relationship tables derived from bridge BIM data. In addition, a few-shot learning-based prompt design is utilized to generate Cypher queries from natural-language inputs automatically. The proposed framework is implemented as the Graph-ACQ system and validated using rigid-frame bridge BIM data. Experimental results demonstrate 100% accuracy in schema validity and query generation, with an average processing time of 7.1s. The proposed approach enables intuitive, relationship-oriented BIM data querying and supports scalable application across diverse infrastructure domains.

단백질간 구조 비교는 기능적 또는 구조적으로 연관된 단백질을 분류하거나 모티프(motif)를 찾는데 유용하게 사용되고 있다. 여러 가지 단백질간 구조 비교 방법 중에서 단백질 2차구조를 이용하는 방법은 실행속도의 측면에서 장점이 있다. 본 논문에서는 단백질 2차 구조와 그들 사이의 관계를 기반으로 한 단백질 구조 비교에서 사용될 유사성 그래프를 생성하는 방법을 기술하였다. 유사성 그래프는 단백질의 2차구조 사이의 관계를 노드로 하여 생성되는데, 그 시간복잡도가 O(n$^4$)이다. 이에 본 논문에서는 유사성 그래프의 생성을 효율적으로 할 수 있는 알고리즘을 개발하였다.

악성코드 분석을 위한 기술 중 하나로 실행 프로그램의 함수 호출 관계를 시퀀스 또는 그래프 작성한 후, 그 결과를 분석하는 기술이 제안되었다. 이러한 기술들은 일반적으로 실행 프로그램 파일의 정적 분석을 통해 함수 호출 코드를 분석하고, 함수 호출 관계를 시퀀스 또는 그래프로 정리한다. 그러나 난독화 된 실행 프로그램의 경우, 실행 프로그램 파일의 구성이 표준구성과 다르기 때문에 정적분석 만으로는 함수 호출관계를 명확히 분석하기 어렵다. 본 논문에서는 난독화 된 실행 프로그램의 함수 호출관계를 분석하기 위한 동적 분석 방법을 제안하고, 제안된 기술을 이용하여 함수 호출관계를 그래프로 구성하는 방법을 제안한다.

As one of the techniques for analyzing malicious code, techniques creating a sequence or a graph of function call relationships in an executable program and then analyzing the result are proposed. Such methods generally study function calling in the executable program code through static analysis and organize function call relationships into a sequence or a graph. However, in the case of an obfuscated executable program, it is difficult to analyze the function call relationship only with static analysis because the structure/content of the executable program file is different from the standard structure/content. In this paper, we propose a dynamic analysis method to analyze the function call relationship of an obfuscated execution program. We suggest constructing a function call relationship as a graph using the proposed technique.

소프트웨어 테스팅은 소프트웨어의 개발 과정에 있어서 가장 중요하고 많은 비용이 드는 부분이다. 소프트웨어 테스팅을 수동으로 행하는 것은 많은 문제를 발생시킬 수 있다. 소프트웨어 자동 테스팅을 하기 위해서 최근 활발히 연구되고 있는 부분이 모델 기반 소프트웨어 자동 테스팅 기법이다. 본 논문에서는 UML 모델 기반 테스트 케이스 자동 생성 기법을 제안한다. UML state chart 로 모델링 된 테스트 대상 소프트웨어를 제안된 자료구조에 저장 한 후, 이를 flow graph 로 변환한다. 최종적으로 변환된 flow graph 에서 테스트 케이스를 생성한다.

디지탈화된 지형 정보는 조망분석, 토목계획이나 설계, 또는 지리정보시스템등 여러 분야 에 필요한 요소가 된다. 또한 컴퓨터에 적절한 형식으로 입력된 지형정보는 모의 비행훈련이나 무인비행장치에서도 사용될 수 있다. 지형정보는 지도위에 등고선을 비롯한 여러가지 기호들로 표시되어 있어서 훈련된 요원에 의해 분석된다. 자동분석을 위해서는 컴퓨터에 입력되어야 하는 데 디지타이징 타블렛과 같은 장비를 사용하여 수동으로 입력하는 것은 많은 시간과 인력을 필요 로 한다. 본 논문에서는 이차원 지형도로부터 삼차원 지형정보를 자동적으로 추출하는 방법을 다 루고 있다. 등고선 조각연결 알고리즘을 포함하는 몇 가지 알고리즘들이 제안되었고 실제 지형도 를 사용하여 실험되었다.

Digitalized topographic information is necessary for many areas such as landscape analysis, civil engineering planning and design, and geographic information systems. It can also be used in flight simulator and automatic navigation of unmanned plane if it is stored in computer in relevant format. Topographic information is coded with various symbols including contour lines, and is analyzed by trained personnels. The information should be stored in computer for automatic analysis, but it requires a lot of time and manpower to enter the contours using manual input devices such as digitizing tablet. This paper deals with automatic extraction and reconstruction of 3D topographic information from 2D terrain map. Several algorithms were developed in this work including contour segment finding algorithm and contour segment linking algorithm. The algorithm were tested using real 2D terrain map.

In this paper, we have proposed an efficient test generation method for asynchronous circuits. The test generation is based on specification level, especially on Signal Transition Graph(STG)〔1〕 which is a kind of specification method for asynchronous circuits. To conduct a high-level test generation, we have defined a high-level fault model, called single State Transition Fault(STF) model on STG and proposed a test generation algorithm for STF model. The effectiveness of the proposed fault model and its test generation algorithm is shown by experimental results on a set of benchmarks given in the form of STG. Experimental results show that the generated test for the proposed fault model achieves high fault coverage over single input stuck-at fault model with low cost. We have also proposed extended STF model with additional gate-level information to achieve higher fault coverage in cost of longer execution time.

기존의 정보 추출에서는 웹 문서의 구조가 변경되었을 때 Wrapper가 원하는 정보를 추출할 수 없었다. 또한 웹 문서의 구조가 바뀌는 경우 동일한 정보를 Wrapping함에도 불구하고 사용자는 정보를 추출 할 수 없었던 이유를 찾지 못하는 경우가 대부분이었다. 이 문제를 해결하기 위해 본 논문에서는 Web 페이지를 시각적 블록 단위로 잘라 인접한 블록들을 통해 그래프를 형성하여 웹 문서의 구조가 일부 변경되어도 기존의 Wrapper를 통해 정보를 추출할 수 있도록 보다 효율적으로 Wrapper를 생성하고 유지관리 하는 방법을 제안한다. 또한 웹 문서를 블록 단위로 분할하여 그래프를 생성함으로써 블록 내부에 추출하고자 하는 정보에 대한 규칙이 좀 더 유연하게 표현 될 수 있으며 문서의 구조가 아닌 추출하고자 하는 정보를 중심으로 규칙을 생성함으로써 그래프의 구조뿐 아니라 그래프를 구성하고 있는 블록 내부의 구조가 일부 변하더라도 기존의 규칙을 이용하여 정보를 추출할 수 있도록 하였다.