165.80/130.53 YES 165.80/130.54 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 165.80/130.54 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 165.80/130.54 165.80/130.54 165.80/130.54 Termination of the given C Problem could be proven: 165.80/130.54 165.80/130.54 (0) C Problem 165.80/130.54 (1) CToLLVMProof [EQUIVALENT, 169 ms] 165.80/130.54 (2) LLVM problem 165.80/130.54 (3) LLVMToTerminationGraphProof [EQUIVALENT, 127.5 s] 165.80/130.54 (4) LLVM Symbolic Execution Graph 165.80/130.54 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 165.80/130.54 (6) LLVM Symbolic Execution SCC 165.80/130.54 (7) SCC2IRS [SOUND, 95 ms] 165.80/130.54 (8) IntTRS 165.80/130.54 (9) IntTRSCompressionProof [EQUIVALENT, 0 ms] 165.80/130.54 (10) IntTRS 165.80/130.54 (11) PolynomialOrderProcessor [EQUIVALENT, 12 ms] 165.80/130.54 (12) YES 165.80/130.54 165.80/130.54 165.80/130.54 ---------------------------------------- 165.80/130.54 165.80/130.54 (0) 165.80/130.54 Obligation: 165.80/130.54 c file /export/starexec/sandbox/benchmark/theBenchmark.c 165.80/130.54 ---------------------------------------- 165.80/130.54 165.80/130.54 (1) CToLLVMProof (EQUIVALENT) 165.80/130.54 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 165.80/130.54 ---------------------------------------- 165.80/130.54 165.80/130.54 (2) 165.80/130.54 Obligation: 165.80/130.54 LLVM Problem 165.80/130.54 165.80/130.54 Aliases: 165.80/130.54 165.80/130.54 Data layout: 165.80/130.54 165.80/130.54 "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" 165.80/130.54 165.80/130.54 Machine: 165.80/130.54 165.80/130.54 "x86_64-pc-linux-gnu" 165.80/130.54 165.80/130.54 Type definitions: 165.80/130.54 165.80/130.54 Global variables: 165.80/130.54 165.80/130.54 Function declarations and definitions: 165.80/130.54 165.80/130.54 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 165.80/130.54 *BasicFunctionTypename: "cstrcpy" linkageType: EXTERNALLY_VISIBLE returnParam: *i8 parameters: (s1 *i8, s2 *i8) variableLength: false visibilityType: DEFAULT callingConvention: ccc 165.80/130.54 0: 165.80/130.54 %1 = alloca *i8, align 8 165.80/130.54 %2 = alloca *i8, align 8 165.80/130.54 %dst = alloca *i8, align 8 165.80/130.54 %src = alloca *i8, align 8 165.80/130.54 store %s1, %1 165.80/130.54 store %s2, %2 165.80/130.54 %3 = load %1 165.80/130.54 store %3, %dst 165.80/130.54 %4 = load %2 165.80/130.54 store %4, %src 165.80/130.54 br %5 165.80/130.54 5: 165.80/130.54 %6 = load %src 165.80/130.54 %7 = getelementptr %6, 1 165.80/130.54 store %7, %src 165.80/130.54 %8 = load %6 165.80/130.54 %9 = load %dst 165.80/130.54 %10 = getelementptr %9, 1 165.80/130.54 store %10, %dst 165.80/130.54 store %8, %9 165.80/130.54 %11 = sext i8 %8 to i32 165.80/130.54 %12 = icmp ne %11 0 165.80/130.54 br %12, %13, %14 165.80/130.54 13: 165.80/130.54 br %5 165.80/130.54 14: 165.80/130.54 %15 = load %1 165.80/130.54 ret %15 165.80/130.54 165.80/130.54 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 165.80/130.54 0: 165.80/130.54 %1 = alloca i32, align 4 165.80/130.54 %length1 = alloca i32, align 4 165.80/130.54 %length2 = alloca i32, align 4 165.80/130.54 %nondetArea = alloca *i8, align 8 165.80/130.54 %nondetString = alloca *i8, align 8 165.80/130.54 store 0, %1 165.80/130.54 %2 = call i32 @__VERIFIER_nondet_int() 165.80/130.54 store %2, %length1 165.80/130.54 %3 = call i32 @__VERIFIER_nondet_int() 165.80/130.54 store %3, %length2 165.80/130.54 %4 = load %length1 165.80/130.54 %5 = icmp slt %4 1 165.80/130.54 br %5, %6, %7 165.80/130.54 6: 165.80/130.54 store 1, %length1 165.80/130.54 br %7 165.80/130.54 7: 165.80/130.54 %8 = load %length2 165.80/130.54 %9 = icmp slt %8 1 165.80/130.54 br %9, %10, %11 165.80/130.54 10: 165.80/130.54 store 1, %length2 165.80/130.54 br %11 165.80/130.54 11: 165.80/130.54 %12 = load %length1 165.80/130.54 %13 = load %length2 165.80/130.54 %14 = icmp slt %12 %13 165.80/130.54 br %14, %15, %16 165.80/130.54 15: 165.80/130.54 store 0, %1 165.80/130.54 br %33 165.80/130.54 16: 165.80/130.54 %17 = load %length1 165.80/130.54 %18 = sext i32 %17 to i64 165.80/130.54 %19 = mul %18 1 165.80/130.54 %20 = alloca i8, numElementsLit: %19 165.80/130.54 store %20, %nondetArea 165.80/130.54 %21 = load %length2 165.80/130.54 %22 = sext i32 %21 to i64 165.80/130.54 %23 = mul %22 1 165.80/130.54 %24 = alloca i8, numElementsLit: %23 165.80/130.54 store %24, %nondetString 165.80/130.54 %25 = load %length2 165.80/130.54 %26 = sub %25 1 165.80/130.54 %27 = sext i32 %26 to i64 165.80/130.54 %28 = load %nondetString 165.80/130.54 %29 = getelementptr %28, %27 165.80/130.54 store 0, %29 165.80/130.54 %30 = load %nondetArea 165.80/130.54 %31 = load %nondetString 165.80/130.54 %32 = call *i8 @cstrcpy(*i8 %30, *i8 %31) 165.80/130.54 store 0, %1 165.80/130.54 br %33 165.80/130.54 33: 165.80/130.54 %34 = load %1 165.80/130.54 ret %34 165.80/130.54 165.80/130.54 165.80/130.54 Analyze Termination of all function calls matching the pattern: 165.80/130.54 main() 165.80/130.54 ---------------------------------------- 165.80/130.54 165.80/130.54 (3) LLVMToTerminationGraphProof (EQUIVALENT) 165.80/130.54 Constructed symbolic execution graph for LLVM program and proved memory safety. 165.80/130.54 ---------------------------------------- 165.80/130.54 165.80/130.54 (4) 165.80/130.54 Obligation: 165.80/130.54 SE Graph 165.80/130.54 ---------------------------------------- 165.80/130.54 165.80/130.54 (5) SymbolicExecutionGraphToSCCProof (SOUND) 165.80/130.54 Splitted symbolic execution graph to 1 SCC. 165.80/130.54 ---------------------------------------- 165.80/130.54 165.80/130.54 (6) 165.80/130.54 Obligation: 165.80/130.54 SCC 165.80/130.54 ---------------------------------------- 165.80/130.54 165.80/130.54 (7) SCC2IRS (SOUND) 165.80/130.54 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 165.80/130.54 Generated rules. Obtained 14 rulesP rules: 165.80/130.54 f_517(v430, v431, v432, v433, v434, v435, v437, v438, v439, v440, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, 0, v447, v448, v450, 3, 7, 2, 4, 8) -> f_518(v430, v431, v432, v433, v434, v435, v437, v463, v438, v439, v440, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, 0, v447, v448, v450, 3, 7, 2, 4, 8) :|: v463 = 1 + v437 && 3 <= v463 165.80/130.54 f_518(v430, v431, v432, v433, v434, v435, v437, v463, v438, v439, v440, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, 0, v447, v448, v450, 3, 7, 2, 4, 8) -> f_519(v430, v431, v432, v433, v434, v435, v437, v463, v438, v439, v440, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, 0, v447, v448, v450, 3, 7, 2, 4, 8) :|: TRUE 165.80/130.54 f_519(v430, v431, v432, v433, v434, v435, v437, v463, v438, v439, v440, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, 0, v447, v448, v450, 3, 7, 2, 4, 8) -> f_520(v430, v431, v432, v433, v434, v435, v437, v463, v465, v439, v440, v438, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, 0, v447, v448, v450, 3, 7, 2, 4, 8) :|: TRUE 165.80/130.54 f_520(v430, v431, v432, v433, v434, v435, v437, v463, v465, v439, v440, v438, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, 0, v447, v448, v450, 3, 7, 2, 4, 8) -> f_521(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v438, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) :|: 0 = 0 165.80/130.54 f_521(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v438, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) -> f_522(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, v438, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) :|: v467 = 1 + v440 && 3 <= v467 && 3 <= v457 165.80/130.54 f_522(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, v438, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) -> f_523(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, v438, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) :|: TRUE 165.80/130.54 f_523(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, v438, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) -> f_524(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, v438, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) :|: TRUE 165.80/130.54 f_524(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, v438, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) -> f_525(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v438, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) :|: 0 = 0 165.80/130.54 f_525(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v438, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) -> f_526(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v438, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) :|: v465 != 0 && v437 < v451 && 3 <= v451 165.80/130.54 f_526(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v438, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) -> f_528(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v438, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) :|: 0 = 0 165.80/130.54 f_528(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v438, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) -> f_530(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v438, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) :|: TRUE 165.80/130.54 f_530(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v438, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) -> f_532(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v438, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) :|: TRUE 165.80/130.54 f_532(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, v438, v439, 0, v447, v448, v450, 3, 7, 2, 4, 8) -> f_516(v430, v431, v432, v433, v434, v435, v437, v463, v465, v440, v467, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, 0, v447, v448, v450, 3, 7, 2, 4, 8) :|: TRUE 165.80/130.54 f_516(v430, v431, v432, v433, v434, v435, v436, v437, v438, v439, v440, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, 0, v447, v448, v450, 3, 7, 2, 4, 8) -> f_517(v430, v431, v432, v433, v434, v435, v437, v438, v439, v440, 1, v442, v452, v443, v453, v444, v454, v445, v455, v446, v456, v457, v451, v458, v459, v460, v461, v462, v436, 0, v447, v448, v450, 3, 7, 2, 4, 8) :|: 0 = 0 165.80/130.54 Combined rules. Obtained 2 rulesP rules: 165.80/130.54 f_517(v430:0, v431:0, v432:0, v433:0, v434:0, v435:0, v437:0, v438:0, v439:0, v440:0, 1, v442:0, v452:0, v443:0, v453:0, v444:0, v454:0, v445:0, v455:0, v446:0, v456:0, v457:0, v451:0, v458:0, v459:0, v460:0, v461:0, v462:0, v436:0, 0, v447:0, v448:0, v450:0, 3, 7, 2, 4, 8) -> f_517(v430:0, v431:0, v432:0, v433:0, v434:0, v435:0, 1 + v437:0, v465:0, v440:0, 1 + v440:0, 1, v442:0, v452:0, v443:0, v453:0, v444:0, v454:0, v445:0, v455:0, v446:0, v456:0, v457:0, v451:0, v458:0, v459:0, v460:0, v461:0, v462:0, v437:0, 0, v447:0, v448:0, v450:0, 3, 7, 2, 4, 8) :|: v437:0 > 1 && v440:0 > 1 && v457:0 > 2 && v451:0 > v437:0 && v451:0 > 2 && v465:0 < 0 165.80/130.54 f_517(v430:0, v431:0, v432:0, v433:0, v434:0, v435:0, v437:0, v438:0, v439:0, v440:0, 1, v442:0, v452:0, v443:0, v453:0, v444:0, v454:0, v445:0, v455:0, v446:0, v456:0, v457:0, v451:0, v458:0, v459:0, v460:0, v461:0, v462:0, v436:0, 0, v447:0, v448:0, v450:0, 3, 7, 2, 4, 8) -> f_517(v430:0, v431:0, v432:0, v433:0, v434:0, v435:0, 1 + v437:0, v465:0, v440:0, 1 + v440:0, 1, v442:0, v452:0, v443:0, v453:0, v444:0, v454:0, v445:0, v455:0, v446:0, v456:0, v457:0, v451:0, v458:0, v459:0, v460:0, v461:0, v462:0, v437:0, 0, v447:0, v448:0, v450:0, 3, 7, 2, 4, 8) :|: v437:0 > 1 && v440:0 > 1 && v457:0 > 2 && v451:0 > v437:0 && v451:0 > 2 && v465:0 > 0 165.80/130.54 Filtered unneeded arguments: 165.80/130.54 f_517(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34, x35, x36, x37, x38) -> f_517(x7, x10, x22, x23) 165.80/130.54 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 165.80/130.54 f_517(v437:0, v440:0, v457:0, v451:0) -> f_517(1 + v437:0, 1 + v440:0, v457:0, v451:0) :|: v440:0 > 1 && v437:0 > 1 && v457:0 > 2 && v451:0 > 2 && v451:0 > v437:0 165.80/130.54 165.80/130.54 ---------------------------------------- 165.80/130.54 165.80/130.54 (8) 165.80/130.54 Obligation: 165.80/130.54 Rules: 165.80/130.54 f_517(v437:0, v440:0, v457:0, v451:0) -> f_517(1 + v437:0, 1 + v440:0, v457:0, v451:0) :|: v440:0 > 1 && v437:0 > 1 && v457:0 > 2 && v451:0 > 2 && v451:0 > v437:0 165.80/130.54 165.80/130.54 ---------------------------------------- 165.80/130.54 165.80/130.54 (9) IntTRSCompressionProof (EQUIVALENT) 165.80/130.54 Compressed rules. 165.80/130.54 ---------------------------------------- 165.80/130.54 165.80/130.54 (10) 165.80/130.54 Obligation: 165.80/130.54 Rules: 165.80/130.54 f_517(v437:0:0, v440:0:0, v457:0:0, v451:0:0) -> f_517(1 + v437:0:0, 1 + v440:0:0, v457:0:0, v451:0:0) :|: v451:0:0 > 2 && v451:0:0 > v437:0:0 && v457:0:0 > 2 && v437:0:0 > 1 && v440:0:0 > 1 165.80/130.54 165.80/130.54 ---------------------------------------- 165.80/130.54 165.80/130.54 (11) PolynomialOrderProcessor (EQUIVALENT) 165.80/130.54 Found the following polynomial interpretation: 165.80/130.54 [f_517(x, x1, x2, x3)] = -x + x3 165.80/130.54 165.80/130.54 The following rules are decreasing: 165.80/130.54 f_517(v437:0:0, v440:0:0, v457:0:0, v451:0:0) -> f_517(1 + v437:0:0, 1 + v440:0:0, v457:0:0, v451:0:0) :|: v451:0:0 > 2 && v451:0:0 > v437:0:0 && v457:0:0 > 2 && v437:0:0 > 1 && v440:0:0 > 1 165.80/130.54 The following rules are bounded: 165.80/130.54 f_517(v437:0:0, v440:0:0, v457:0:0, v451:0:0) -> f_517(1 + v437:0:0, 1 + v440:0:0, v457:0:0, v451:0:0) :|: v451:0:0 > 2 && v451:0:0 > v437:0:0 && v457:0:0 > 2 && v437:0:0 > 1 && v440:0:0 > 1 165.80/130.54 165.80/130.54 ---------------------------------------- 165.80/130.54 165.80/130.54 (12) 165.80/130.54 YES 166.06/130.61 EOF