이 논문은 LR 파서를 활용한 텍스트 기반 문법 완성(syntax completion) 기법을 제안한다. 우리는 문장의 형태(sentential forms)에 기반하여 자동완성할 텍스트 후보의 형식을 형식적으로 정의하고, LR 파싱 과정에서의 축소(reduction)를 이용해 이러한 후보를 계산하는 기본 알고리즘을 설계하였다. 이는 대부분의 기존 기법들이 후보의 정의를 비형식적으로 제공하는 것과 다르며, LR 파서를 사용하는 기존 문법 변환 기반 방식들과 달리 복잡한 변환 작업 없이도 사용이 가능하다는 점에서 차별된다. 제안된 방식은 LR 파서를 수정하지 않고 그대로 사용할 수 있으며, 추가적인 부담 없이 문법 완성 시스템을 구축할 수 있도록 한다. 실용적 적용을 위해, 우리는 정제된 후보 정의와 새로운 전략을 도입하여 기본 알고리즘을 확장하였다. 이 확장된 알고리즘은 기존 기법보다 현실적인 프로그래밍 언어 문법에 더 적합한 후보들을 계산할 수 있다. 구현은 Emacs 서버 상에서 이루어졌으며, Small Basic, C, Haskell 세 가지 실제 프로그래밍 언어로 평가하였다. 평가 결과, 전체 후보의 절반은 0.2초 이내에 계산되었고, 약 89.2%는 1초 이내에 계산되었으며, 나머지는 시간이 오래 걸렸다. 우리는 이러한 평가 결과를 논문에서 자세히 논의한다.
This paper presents a text-based syntax completion method that uses an LR parser. We propose formal definitions of candidate text to be completed based on the sentential forms. Moreover, we design basic algorithms for computing candidate texts through reductions in the LR parsing. This is unlike most existing methods, wherein the definition of candidates that are intended to be generated are given informally. In addition, this is unlike grammar transformation approaches that use LR parsers and is a currently burdensome task. The proposed method allows LR parsers to be adopted without modification and a syntax completion system to be built without incurring efforts. For practical purposes, we extended the basic algorithms using a new definition of refined candidates and a new strategy. The extended algorithms can compute more useful candidates for realistic programming language grammars than those of existing ones; Further, we implemented the algorithms on an Emacs server to demonstrate the feasibility of their application. We evaluated the extended algorithm with three real-world programming languages, Small Basic, C, and Haskell. The extended algorithm computes half of all candidates in less than or equal to 0.2 seconds and 89.2\% in approximately one second in the evaluation while computing the remaining candidates took a long time. We discuss its evaluation in detail.
(See Ranked Syntax Completion Using LR Parsing for the full paper.)
The polymorphic RPC calculus allows programmers to write succinct multitier programs using polymorphic location constructs. However, until now it lacked an implementation. We develop an experimental programming language based on the polymorphic RPC calculus. We introduce a polymorphic Client-Server (CS) calculus with the client and server parts separated. In contrast to existing untyped CS calculi, our calculus is not only able to resolve polymorphic locations statically, but it is also able to do so dynamically. We design a type-based slicing compilation of the polymorphic RPC calculus into this CS calculus, proving type and semantic correctness. We propose a method to erase types unnecessary for execution but retaining locations at runtime by translating the polymorphic CS calculus into an untyped CS calculus, proving semantic correctness.
본 논문은 LR 파서를 쉽게 개발하기 위하여 두 가지 아이디어를 제안한다. 첫째, 오토마타 생 성을 모듈화하여 새로운 프로그래밍 언어를 위한 파서 생성 도구를 쉽게 개발 할 수 있다. 둘째, 파서 명 세를 일반 프로그래밍언어로 작성하도록 구성하여 이 언어 개발 환경에서 제공하는 구문 오류, 자동 완성, 타입 오류 검사 기능들을 이용하여 파서 명세의 오류를 바로잡을 수 있다. 이 연구에서 제안한 아이디어 로 Python, Java, C++, Haskell로 파서를 작성할 수 있는 도구를 개발하였고, 실험을 통하여 위 두 가지 장점을 보였다.
This paper proposes two ways to develop LR parsers easily. First, one can write a parser specification in a general programming language and derive the benefits of syntax error checking, code completion, and type-error checking over the specification from the language’s development environment. Second, to make it easy to develop a parser tool for a new programming language, the automata generation for the parser specifications is in a modular form. With the idea proposed in this study, we developed a tool for writing parsers in Python, Java, C++, and Haskell. We also demonstrated the two aforementioned advantages in an experiment.
자체 수정 코드(Self-Modifying-Code)란 실행 시간 동안 스스로 실행 코드를 변경하는 코드를 말한다. 이런 기법은 특히 악성코드가 정적 분석을 우회하는 데 악용된다. 따라서 이러한 악성코드를 효과적으로 검출하려면 자체 수정 코드를 파악하는 것이 중요하다. 그동안 동적 분석 방법으로 자체 수정 코드를 분석해왔으나 이는 시간과 비용이 많이 든다. 만약 정적 분석으로 자체 수정 코드를 검출할 수 있다면 악성코드 분석에 큰 도움이 될 것이다. 본 논문에서는 LLVM IR로 변환한 바이너리 실행 프로그램을 대상으로 자체 수정 코드를 탐지하는 정적 분석방법을 제안하고, 자체 수정 코드 벤치마크를 만들어 이 방법을 적용했다. 본 논문의 실험 결과 벤치마크 프로그램을 컴파일로 변환한 최적화된 형태의 LLVM IR 프로그램에 대해서는 설계한 정적 분석 방법이 효과적이었다. 하지만 바이너리를 리프팅 변환한 비정형화된 LLVM IR 프로그램에 대해서는 자체 수정 코드를 검출하기 어려운 한계가 있었다. 이를 극복하기 위해 바이너리를 리프팅 하는 효과적인 방법이 필요하다.
Self-Modifying-Code is a code that changes the code by itself during execution time. This technique is particularly abused by malicious code to bypass static analysis. Therefor, in order to effectively detect such malicious codes, it is important to identify self-modifying-codes. In the meantime, Self-modify-codes have been analyzed using dynamic analysis methods, but this is time-consuming and costly. If static analysis can detect self-modifying-code it will be of great help to malicious code analysis. In this paper, we propose a static analysis method to detect self-modified code for binary executable programs converted to LLVM IR and apply this method by making a self-modifying-code benchmark. As a result of the experiment in this paper, the designed static analysis method was effective for the standardized LLVM IR program that was compiled and converted to the benchmark program. However, there was a limitation in that it was difficult to detect the self-modifying-code for the unstructured LLVM IR program in which the binary was lifted and transformed. To overcome this, we need an effective way to lift the binary code.