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
Dans les multiprocesseurs, des modèles de mémoire sont introduits pour décrire les exécutions de programmes entre processeurs. Les modèles de mémoire assouplis, qui assouplissent l'ordre des exécutions, sont utilisés dans la plupart des processeurs modernes, tels que ARM et POWER. Étant donné qu'un modèle de mémoire assoupli pourrait modifier la sémantique du programme, les exécutions des programmes pourraient ne pas être les mêmes que nos attentes, qui devraient préserver l'exactitude du programme. En plus des modèles de mémoire assouplis, la manière d'exécuter une instruction est décrite par une sémantique d'instruction, qui varie selon les architectures de processeur. Traiter la sémantique des instructions parmi une variété de programmes assembleur est un défi pour la vérification des programmes. Ainsi, cet article propose un moyen de vérifier une variété de programmes assembleurs exécutés sous un modèle de mémoire détendu. La variété des programmes d'assemblage peut être résumée comme la manière d'exécuter les programmes en introduisant une structure opérationnelle. En outre, il existe des cadres existants pour modéliser des modèles de mémoire détendus, qui peuvent réaliser des exécutions de programme à vérifier avec une propriété de programme. Notre travail adopte un solveur SMT pour révéler automatiquement les exécutions du programme sous un modèle de mémoire et vérifier si les exécutions violent ou non la propriété du programme. S'il y a une exécution à partir du solveur, l'exactitude du programme n'est pas préservée dans le modèle de mémoire assoupli. Pour vérifier les programmes, un outil expérimental a été développé pour coder les programmes donnés pour un modèle de mémoire dans une formule du premier ordre qui viole l'exactitude du programme. L'outil adopte un cadre de modélisation pour coder les programmes dans une formule pour le solveur SMT. Le solveur trouve alors automatiquement une valorisation qui satisfait la formule. Dans nos expériences, deux méthodes de codage ont été implémentées sur la base de deux frameworks de modélisation. Les valorisations résultantes du solveur peuvent être considérées comme les bugs survenus dans les programmes originaux.
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.
Copier
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
Copier
@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},}
Copier
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 -