progge.rs
1.0.0
Proggers est un terrain de jeu d'analyse de programme pour une langue simple et impérative.
Dépendances:
Ni Elina ni LLVM ni Z3 ne sont nécessaires pour la vérification du type et la visualisation CFG, ils pourraient donc être transformés en une caractéristique de caisse. S'il vous plaît, n'hésitez pas à contribuer!
Une fois les conditions préalables installées, vous pouvez installer des proggers avec: cargo install --git https://github.com/skius/progge.rs
proggers
<sourcefile> # the sourcefile to analyze
--cfg # visualize the control flow graph
--typecheck # type-check the source
--analyze # shorthand for --symex --ai
--symex # run symbolic execution
--ai # run abstract interpretation
--ast # print the abstract syntax tree
-o <outputfile> # compile source into the executable <outputfile>
--verbose # print LLVM IR when compiling
Les progressifs peuvent analyser des programmes écrits dans la langue progressive.
program: funcdef*
funcdef: fn var((var: type,)*) -> type { block }
block: stmt;*
stmt: let var = expr
| var = expr
| expr[expr] = expr
| var(expr,*)
| testcase!
| unreachable!
| if expr { block } [ else { block } ]
| while expr { block }
| return [expr]
expr: var
| int
| bool
| expr binop expr
| unop expr
| var(expr,*)
| [expr,*]
| [expr; expr]
binop: + | - | * | / | % | < | <= | > | >= | == | !=
unop: - | !
var: [A-Za-z_][A-Za-z0-9_]*
type: int | bool | [type]
Rien de spécial. Les liaisons de location sont autorisées à fantasmer des liaisons précédentes.
Build-in spéciaux de Progge et quelle partie des progressages les utilise:
| Intégré | Description | IA | SE | TC | C |
|---|---|---|---|---|---|
unreachable! | Affirme que le flux de contrôle peut ne jamais atteindre cette déclaration | [x] | [x] | ||
testcase! | Instruit la génération de cas de test qui atteignent cette déclaration | [x] | [x] | ||
assume!(expr) | Suppose que l'expression de bool donnée comme vrai | [x] | [x] | ||
analyze!(expr) | Demande à l'analyse numérique d'imprimer une extérieur excessive de l'expression int | [x] | |||
int_arg(expr) | Renvoie l'argument de la ligne de commande expr-th converti en un int | [x] | [x] | ||
print_int(expr) | Imprime l'INT donné à stdout | [x] |
Légende : TC: Type-Checking, SE: Exécution symbolique, AI: Résumé Interpertation, C: Compilation
Les proggers sont capables d'analyser le programme ci-dessous et de trouver des valeurs de retour possibles, comme on peut le voir en bas à droite " z: [-1,0] " indiquant que z peut être -1 ou 0 .
fn analyze ( x : int , y : int ) -> int {
if x < y {
while x < y {
x = x + 1 ;
y = y - 1 ;
}
let z = y - x ;
return z ;
}
return - 2 ;
} 
Les progressifs soutiennent également quelques directives qui utilisent les résultats d'interprétation abstraits.
analyser! : Imprime explicitement les valeurs possibles pour une expression donnée. Par exemple, Running proggers --typecheck --analyze analyzer-examples/analyze_loop.progge donne la rétroaction suivante (l'image ne montre pas la sortie complète):
Notez que les valeurs possibles renvoyées pour une expression sont une sur-approximation .
inaccessible! : Affirme qu'une déclaration est inaccessible. Par exemple, la course proggers --typecheck --analyze analyzer-examples/unreachable.progge donne la rétroaction suivante:
Notez qu'encore une analyse inaccessible en utilisant une interprétation abstraite calcule une excession excessive - c'est-à-dire qu'elle peut donner de faux positifs (avertir des déclarations accessibles unreachable! Qui sont en vérité inaccessibles), mais ne peuvent jamais donner de faux négatifs (s'il n'y a pas d'avertissements sur un unreachable! Alors il est garanti que la déclaration est inaccessible). Voir l'exécution symbolique pour les déclarations garanties sur l'accouchement.
L'interprétation abstraite (Wikipedia) calcule une sur-approximation, ce qui signifie que tous les comportements du programme possibles (peut-être plus, mais pas moins) sont capturés par celui-ci, c'est-à-dire que l'implication est "si le véritable programme présente un comportement, alors ce comportement est contenu dans la surexploitation de l'interprétation abstraite".
En bref, l'interprétation abstraite peut prouver l'absence de comportements de programme indésirables, qui pourraient être par exemple les exceptions d'index out des limites (TODO), l'exécution d' unreachable! Des déclarations ou des appels de fonction dont les arguments ne satisfont pas aux conditions préalables de la fonction.
Testcase! : Génère des tests de test (c.-à-t-peu de valeurs d'argument pour la fonction) qui atteignent l'instruction. Par exemple, Running proggers --typecheck --symex analyzer-examples/symex_arr_hard.progge donne:
Remarque: la génération de TestCase fonctionne également pour les appels à int_arg - voir symex_blackbox.progge
analyzer-examples/symex_arr_hard.progge:7:13: sample inputs reaching this statement:
{ x = 1, y = 0 }
{ x = 0, y = 1 }
{ x = 0, y = 2 }
{ x = 2, y = 1 }
{ x = 1, y = 2 }
inaccessible! : De plus, si une unreachable! n'est pas réellement inaccessible, l'exécution symbolique lancera une erreur et donnera un échantillon d'entrée qui atteint l'instruction. Par exemple, proggers --typecheck --symex analyzer-examples/unreachable.progge donne: 
L'exécution symbolique (Wikipedia) calcule une sous-approximation, ce qui signifie que l'implication est "si l'exécution symbolique signale un chemin (ensemble de valeurs d'entrée), alors le programme réel doit également suivre ce chemin".
En bref, l'exécution symbolique peut prouver l'accouchement des instructions en donnant des exemples d'exemples concrètes, ou, en d'autres termes, il peut prouver la présence de certains comportements du programme.
let l'observation / portées lexicales: les proggenteurs remarquent qu'il existe cinq variables distinctes appelées x , comme on peut le voir dans l'AST nettoyée que les proggers retournent:
// Original source code
fn analyze ( x : int ) -> int {
x = 0 ;
let x_2 = 10 ;
let x = x ;
let x = x + 1 ;
x_2 = 5 ;
if true {
let x = 2 ;
x = 3 ;
} else {
let x = 4 ;
}
// returns 1
return x ;
}
// Type-checked AST
fn analyze ( x_1 : int ) {
x_1 = 0 ;
let x_2_1 = 10 ;
let x_2 = x_1 ;
let x_3 = ( x_2 + 1 ) ;
x_2_1 = 5 ;
if true {
let x_4 = 2 ;
x_4 = 3 ;
} else {
let x_5 = 4 ;
}
return x_3 ;
}En outre, les progressages sont capables de donner de beaux messages d'erreur (grâce à Ariadne):
// Source
fn foo ( ) -> int {
return true ;
} 
Voir analyzer-examples/tc_bad pour plus d'exemples.
Les progressifs peuvent compiler des programmes vers le code natif.
$ proggers codegen-examples/factorial.progge -t -o factorial
$ ./factorial 4
24
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24Sous licence sous l'un ou l'autre des
à votre option.
À moins que vous ne soyez explicitement indiqué autrement, toute contribution intentionnellement soumise pour inclusion dans les travaux par vous, telle que définie dans la licence Apache-2.0, doit être autorisée à double licence comme ci-dessus, sans aucune condition supplémentaire.
