The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Nos multiprocessadores, modelos de memória são introduzidos para descrever as execuções de programas entre processadores. Modelos de memória relaxada, que relaxam a ordem de execuções, são utilizados na maioria dos processadores modernos, como ARM e POWER. Devido a um modelo de memória relaxado poder alterar a semântica do programa, as execuções dos programas podem não ser as mesmas que esperamos que preservem a correção do programa. Além dos modelos de memória relaxados, a forma de executar uma instrução é descrita por uma semântica de instrução, que varia entre as arquiteturas de processador. Lidar com a semântica de instrução entre uma variedade de programas assembly é um desafio para a verificação do programa. Assim, este artigo propõe uma maneira de verificar uma variedade de programas assembly que são executados sob um modelo de memória relaxado. A variedade de programas assembly pode ser abstraída como a forma de executar os programas, introduzindo uma estrutura de operação. Além disso, existem frameworks para modelagem de modelos de memória relaxados, que podem realizar execuções de programas a serem verificadas com uma propriedade do programa. Nosso trabalho adota um solucionador SMT para revelar automaticamente as execuções do programa sob um modelo de memória e verificar se as execuções violam ou não a propriedade do programa. Se houver alguma execução do solucionador, a correção do programa não será preservada no modelo de memória relaxado. Para verificar os programas, uma ferramenta experimental foi desenvolvida para codificar os programas fornecidos para um modelo de memória em uma fórmula de primeira ordem que viola a correção do programa. A ferramenta adota uma estrutura de modelagem para codificar os programas em uma fórmula para o solucionador SMT. O solucionador então encontra automaticamente uma avaliação que satisfaça a fórmula. Em nossos experimentos, dois métodos de codificação foram implementados com base em duas estruturas de modelagem. As avaliações resultantes do solucionador podem ser consideradas como bugs ocorridos nos programas originais.
Pattaravut MALEEHUAN
Japan Advanced Institute of Science and Technology (JAIST)
Yuki CHIBA
DENSO Corporation
Toshiaki AOKI
Japan Advanced Institute of Science and Technology (JAIST)
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Pattaravut MALEEHUAN, Yuki CHIBA, Toshiaki AOKI, "A Verification Framework for Assembly Programs Under Relaxed Memory Model Using SMT Solver" in IEICE TRANSACTIONS on Information,
vol. E101-D, no. 12, pp. 3038-3058, December 2018, doi: 10.1587/transinf.2018EDP7099.
Abstract: In multiprocessors, memory models are introduced to describe the executions of programs among processors. Relaxed memory models, which relax the order of executions, are used in the most of the modern processors, such as ARM and POWER. Due to a relaxed memory model could change the program semantics, the executions of the programs might not be the same as our expectation that should preserve the program correctness. In addition to relaxed memory models, the way to execute an instruction is described by an instruction semantics, which varies among processor architectures. Dealing with instruction semantics among a variety of assembly programs is a challenge for program verification. Thus, this paper proposes a way to verify a variety of assembly programs that are executed under a relaxed memory model. The variety of assembly programs can be abstracted as the way to execute the programs by introducing an operation structure. Besides, there are existing frameworks for modeling relaxed memory models, which can realize program executions to be verified with a program property. Our work adopts an SMT solver to automatically reveal the program executions under a memory model and verify whether the executions violate the program property or not. If there is any execution from the solver, the program correctness is not preserved under the relaxed memory model. To verify programs, an experimental tool was developed to encode the given programs for a memory model into a first-order formula that violates the program correctness. The tool adopts a modeling framework to encode the programs into a formula for the SMT solver. The solver then automatically finds a valuation that satisfies the formula. In our experiments, two encoding methods were implemented based on two modeling frameworks. The valuations resulted by the solver can be considered as the bugs occurring in the original programs.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018EDP7099/_p
Copiar
@ARTICLE{e101-d_12_3038,
author={Pattaravut MALEEHUAN, Yuki CHIBA, Toshiaki AOKI, },
journal={IEICE TRANSACTIONS on Information},
title={A Verification Framework for Assembly Programs Under Relaxed Memory Model Using SMT Solver},
year={2018},
volume={E101-D},
number={12},
pages={3038-3058},
abstract={In multiprocessors, memory models are introduced to describe the executions of programs among processors. Relaxed memory models, which relax the order of executions, are used in the most of the modern processors, such as ARM and POWER. Due to a relaxed memory model could change the program semantics, the executions of the programs might not be the same as our expectation that should preserve the program correctness. In addition to relaxed memory models, the way to execute an instruction is described by an instruction semantics, which varies among processor architectures. Dealing with instruction semantics among a variety of assembly programs is a challenge for program verification. Thus, this paper proposes a way to verify a variety of assembly programs that are executed under a relaxed memory model. The variety of assembly programs can be abstracted as the way to execute the programs by introducing an operation structure. Besides, there are existing frameworks for modeling relaxed memory models, which can realize program executions to be verified with a program property. Our work adopts an SMT solver to automatically reveal the program executions under a memory model and verify whether the executions violate the program property or not. If there is any execution from the solver, the program correctness is not preserved under the relaxed memory model. To verify programs, an experimental tool was developed to encode the given programs for a memory model into a first-order formula that violates the program correctness. The tool adopts a modeling framework to encode the programs into a formula for the SMT solver. The solver then automatically finds a valuation that satisfies the formula. In our experiments, two encoding methods were implemented based on two modeling frameworks. The valuations resulted by the solver can be considered as the bugs occurring in the original programs.},
keywords={},
doi={10.1587/transinf.2018EDP7099},
ISSN={1745-1361},
month={December},}
Copiar
TY - JOUR
TI - A Verification Framework for Assembly Programs Under Relaxed Memory Model Using SMT Solver
T2 - IEICE TRANSACTIONS on Information
SP - 3038
EP - 3058
AU - Pattaravut MALEEHUAN
AU - Yuki CHIBA
AU - Toshiaki AOKI
PY - 2018
DO - 10.1587/transinf.2018EDP7099
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E101-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2018
AB - In multiprocessors, memory models are introduced to describe the executions of programs among processors. Relaxed memory models, which relax the order of executions, are used in the most of the modern processors, such as ARM and POWER. Due to a relaxed memory model could change the program semantics, the executions of the programs might not be the same as our expectation that should preserve the program correctness. In addition to relaxed memory models, the way to execute an instruction is described by an instruction semantics, which varies among processor architectures. Dealing with instruction semantics among a variety of assembly programs is a challenge for program verification. Thus, this paper proposes a way to verify a variety of assembly programs that are executed under a relaxed memory model. The variety of assembly programs can be abstracted as the way to execute the programs by introducing an operation structure. Besides, there are existing frameworks for modeling relaxed memory models, which can realize program executions to be verified with a program property. Our work adopts an SMT solver to automatically reveal the program executions under a memory model and verify whether the executions violate the program property or not. If there is any execution from the solver, the program correctness is not preserved under the relaxed memory model. To verify programs, an experimental tool was developed to encode the given programs for a memory model into a first-order formula that violates the program correctness. The tool adopts a modeling framework to encode the programs into a formula for the SMT solver. The solver then automatically finds a valuation that satisfies the formula. In our experiments, two encoding methods were implemented based on two modeling frameworks. The valuations resulted by the solver can be considered as the bugs occurring in the original programs.
ER -