Malbolge低級アセンブリプログラミングにおける制御命令の配置設計のためのSATソルバの利用

IR HANDLE Web Site Open Access

Bibliographic Information

Other Title
  • Malbolge テイキュウ アセンブリプログラミング ニ オケル セイギョ メイレイ ノ ハイチ セッケイ ノ タメ ノ SAT ソルバ ノ リヨウ
  • Using SAT Solvers for Solving Control-Instruction Layout Problems in Low-Level Assembly Programming for Malbolge

Search this article

Abstract

Malbolge is known as one of the most esoteric programming languages. Although it became possible to write programs in Malbolge due to the development of the low-level assembly language, we still have a problem that the programming in the low-level assembly language is difficult. This is because for each variable, instructions that take the variable in their arguments are allowed to be placed just above of the variable in the low-level assembly programs, and control-instructions in the low-level assembly language are only unconditional jumps and flip-flop jumps, where the latter alternate jump and no-operations. So far we have to design control structures, i.e., layout of control-instructions, by hand, which is very difficult even if we have an execution tracer for low-level assembly programs. In this paper, to solve this problem, we propose a method to design layout of control-instructions of the low-level assembly language efficiently by using state-of-art SAT solvers. We define a control-instruction layout problem, and propose a SAT encoding for this problem. We also evaluate the performance of control-instruction layout tools based on our method.

IEICE Technical Report;SS2012-50

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top