/export/starexec/sandbox/solver/bin/starexec_run_c /export/starexec/sandbox/benchmark/theBenchmark.c /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- NO proof of /export/starexec/sandbox/benchmark/theBenchmark.c # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given C Problem could be disproven: (0) C Problem (1) CToLLVMProof [EQUIVALENT, 172 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 1062 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToLassoProof [EQUIVALENT, 0 ms] (6) LLVM Symbolic Execution Lasso (7) Lasso2IRS [EQUIVALENT, 110 ms] (8) IntTRS (9) IRS2T2 [EQUIVALENT, 0 ms] (10) T2IntSys (11) T2 [COMPLETE, 812 ms] (12) NO ---------------------------------------- (0) Obligation: c file /export/starexec/sandbox/benchmark/theBenchmark.c ---------------------------------------- (1) CToLLVMProof (EQUIVALENT) Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. ---------------------------------------- (2) Obligation: LLVM Problem Aliases: Data layout: "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" Machine: "x86_64-pc-linux-gnu" Type definitions: Global variables: Function declarations and definitions: *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %a = alloca i32, align 4 %b = alloca i32, align 4 %r = alloca i32, align 4 store 0, %1 %2 = call i32 @__VERIFIER_nondet_int() store %2, %a %3 = call i32 @__VERIFIER_nondet_int() store %3, %b br %4 4: %5 = load %b %6 = icmp sgt %5 0 br %6, %7, %17 7: %8 = call i32 @__VERIFIER_nondet_int() store %8, %r %9 = load %a %10 = sub %9 1 %11 = load %r %12 = sub %10 %11 store %12, %b %13 = load %a %14 = sub %13 1 %15 = load %r %16 = sub %14 %15 store %16, %a br %4 17: ret 0 Analyze Termination of all function calls matching the pattern: main() ---------------------------------------- (3) LLVMToTerminationGraphProof (EQUIVALENT) Constructed symbolic execution graph for LLVM program and proved memory safety. ---------------------------------------- (4) Obligation: SE Graph ---------------------------------------- (5) SymbolicExecutionGraphToLassoProof (EQUIVALENT) Converted SEGraph to 1 independent lasso. ---------------------------------------- (6) Obligation: Lasso ---------------------------------------- (7) Lasso2IRS (EQUIVALENT) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 46 rulesP rules: f_136(v27, v28, v29, v30, v31, v32, v38, 1, v35, v36, v37, v39, v40, v41, v42, 0, 3, 4) -> f_137(v27, v28, v29, v30, v31, v32, v38, 1, v35, v36, v37, v39, v40, v41, v42, 0, 3, 4) :|: 0 < v38 f_137(v27, v28, v29, v30, v31, v32, v38, 1, v35, v36, v37, v39, v40, v41, v42, 0, 3, 4) -> f_139(v27, v28, v29, v30, v31, v32, v38, 1, v35, v36, v37, v39, v40, v41, v42, 0, 3, 4) :|: 0 = 0 f_139(v27, v28, v29, v30, v31, v32, v38, 1, v35, v36, v37, v39, v40, v41, v42, 0, 3, 4) -> f_141(v27, v28, v29, v30, v31, v32, v38, 1, v35, v36, v37, v39, v40, v41, v42, 0, 3, 4) :|: TRUE f_141(v27, v28, v29, v30, v31, v32, v38, 1, v35, v36, v37, v39, v40, v41, v42, 0, 3, 4) -> f_143(v27, v28, v29, v30, v31, v32, v38, 1, v44, v36, v37, v35, v39, v40, v41, v42, 0, 3, 4) :|: TRUE f_143(v27, v28, v29, v30, v31, v32, v38, 1, v44, v36, v37, v35, v39, v40, v41, v42, 0, 3, 4) -> f_144(v27, v28, v29, v30, v31, v32, v38, 1, v44, v36, v37, v35, v39, v40, v41, v42, 0, 3, 4) :|: TRUE f_144(v27, v28, v29, v30, v31, v32, v38, 1, v44, v36, v37, v35, v39, v40, v41, v42, 0, 3, 4) -> f_145(v27, v28, v29, v30, v31, v32, v38, 1, v44, v37, v35, v36, v39, v40, v41, v42, 0, 3, 4) :|: 0 = 0 f_145(v27, v28, v29, v30, v31, v32, v38, 1, v44, v37, v35, v36, v39, v40, v41, v42, 0, 3, 4) -> f_146(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v35, v36, v37, v39, v40, v41, v42, 0, 3, 4) :|: 1 + v46 = v38 && 0 <= v46 f_146(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v35, v36, v37, v39, v40, v41, v42, 0, 3, 4) -> f_147(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v36, v37, v35, v39, v40, v41, v42, 0, 3, 4) :|: 0 = 0 f_147(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v36, v37, v35, v39, v40, v41, v42, 0, 3, 4) -> f_148(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v47, v36, v37, v35, v39, v40, v41, v42, 0, 3, 4) :|: v47 + v44 = v46 f_148(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v47, v36, v37, v35, v39, v40, v41, v42, 0, 3, 4) -> f_149(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v47, v36, v37, v35, v39, v40, v41, v42, 0, 3, 4) :|: TRUE f_149(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v47, v36, v37, v35, v39, v40, v41, v42, 0, 3, 4) -> f_150(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v47, v37, v35, v39, v40, v41, v42, 0, 3, 4) :|: 0 = 0 f_150(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v47, v37, v35, v39, v40, v41, v42, 0, 3, 4) -> f_151(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v47, v35, v39, v40, v41, v42, 0, 3, 4) :|: 1 + v46 = v38 f_151(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v47, v35, v39, v40, v41, v42, 0, 3, 4) -> f_152(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v47, v39, v40, v41, v42, 0, 3, 4) :|: 0 = 0 f_152(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v47, v39, v40, v41, v42, 0, 3, 4) -> f_153(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v49, v39, v40, v41, v42, 0, 3, 4) :|: v49 + v44 = v46 && v47 = v49 f_153(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v49, v39, v40, v41, v42, 0, 3, 4) -> f_154(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v49, v39, v40, v41, v42, 0, 3, 4) :|: TRUE f_154(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v49, v39, v40, v41, v42, 0, 3, 4) -> f_155(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v49, v39, v40, v41, v42, 0, 3, 4) :|: TRUE f_155(v27, v28, v29, v30, v31, v32, v38, 1, v44, v46, v49, v39, v40, v41, v42, 0, 3, 4) -> f_135(v27, v28, v29, v30, v31, v32, v38, 1, v44, v38, v46, v49, v39, v40, v41, v42, 0, 3, 4) :|: TRUE f_135(v27, v28, v29, v30, v31, v32, v33, 1, v35, v36, v37, v38, v39, v40, v41, v42, 0, 3, 4) -> f_136(v27, v28, v29, v30, v31, v32, v38, 1, v35, v36, v37, v39, v40, v41, v42, 0, 3, 4) :|: 0 = 0 f_84 -> f_85(v1, v2, 3, 1, 4) :|: 1 <= v1 && v2 = 3 + v1 && 4 <= v2 f_85(v1, v2, 3, 1, 4) -> f_86(v1, v3, v2, v4, 3, 1, 4) :|: 1 <= v3 && v4 = 3 + v3 && 4 <= v4 f_86(v1, v3, v2, v4, 3, 1, 4) -> f_87(v1, v3, v5, v2, v4, v6, 3, 1, 4) :|: 1 <= v5 && v6 = 3 + v5 && 4 <= v6 f_87(v1, v3, v5, v2, v4, v6, 3, 1, 4) -> f_88(v1, v3, v5, v7, v2, v4, v6, v8, 3, 1, 4) :|: 1 <= v7 && v8 = 3 + v7 && 4 <= v8 f_88(v1, v3, v5, v7, v2, v4, v6, v8, 3, 1, 4) -> f_89(v1, v3, v5, v7, v2, v4, v6, v8, 0, 3, 1, 4) :|: TRUE f_89(v1, v3, v5, v7, v2, v4, v6, v8, 0, 3, 1, 4) -> f_90(v1, v3, v5, v7, v9, v2, v4, v6, v8, 0, 3, 1, 4) :|: TRUE f_90(v1, v3, v5, v7, v9, v2, v4, v6, v8, 0, 3, 1, 4) -> f_91(v1, v3, v5, v7, v9, v2, v4, v6, v8, 0, 3, 1, 4) :|: TRUE f_91(v1, v3, v5, v7, v9, v2, v4, v6, v8, 0, 3, 1, 4) -> f_92(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) :|: TRUE f_92(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) -> f_93(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) :|: TRUE f_93(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) -> f_94(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) :|: TRUE f_94(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) -> f_95(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) :|: 0 = 0 f_95(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) -> f_96(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) :|: 0 < v11 f_96(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) -> f_98(v1, v3, v5, v7, v9, v11, 1, v2, v4, v6, v8, 0, 3, 4) :|: 0 = 0 f_98(v1, v3, v5, v7, v9, v11, 1, v2, v4, v6, v8, 0, 3, 4) -> f_100(v1, v3, v5, v7, v9, v11, 1, v2, v4, v6, v8, 0, 3, 4) :|: TRUE f_100(v1, v3, v5, v7, v9, v11, 1, v2, v4, v6, v8, 0, 3, 4) -> f_102(v1, v3, v5, v7, v9, v11, 1, v13, v2, v4, v6, v8, 0, 3, 4) :|: TRUE f_102(v1, v3, v5, v7, v9, v11, 1, v13, v2, v4, v6, v8, 0, 3, 4) -> f_103(v1, v3, v5, v7, v9, v11, 1, v13, v2, v4, v6, v8, 0, 3, 4) :|: TRUE f_103(v1, v3, v5, v7, v9, v11, 1, v13, v2, v4, v6, v8, 0, 3, 4) -> f_104(v1, v3, v5, v7, v9, v11, 1, v13, v2, v4, v6, v8, 0, 3, 4) :|: 0 = 0 f_104(v1, v3, v5, v7, v9, v11, 1, v13, v2, v4, v6, v8, 0, 3, 4) -> f_105(v1, v3, v5, v7, v9, v11, 1, v13, v15, v2, v4, v6, v8, 0, 3, 4) :|: 1 + v15 = v9 f_105(v1, v3, v5, v7, v9, v11, 1, v13, v15, v2, v4, v6, v8, 0, 3, 4) -> f_106(v1, v3, v5, v7, v9, v11, 1, v13, v15, v2, v4, v6, v8, 0, 3, 4) :|: 0 = 0 f_106(v1, v3, v5, v7, v9, v11, 1, v13, v15, v2, v4, v6, v8, 0, 3, 4) -> f_107(v1, v3, v5, v7, v9, v11, 1, v13, v15, v16, v2, v4, v6, v8, 0, 3, 4) :|: v16 + v13 = v15 f_107(v1, v3, v5, v7, v9, v11, 1, v13, v15, v16, v2, v4, v6, v8, 0, 3, 4) -> f_108(v1, v3, v5, v7, v9, v11, 1, v13, v15, v16, v2, v4, v6, v8, 0, 3, 4) :|: TRUE f_108(v1, v3, v5, v7, v9, v11, 1, v13, v15, v16, v2, v4, v6, v8, 0, 3, 4) -> f_109(v1, v3, v5, v7, v9, v11, 1, v13, v15, v16, v2, v4, v6, v8, 0, 3, 4) :|: 0 = 0 f_109(v1, v3, v5, v7, v9, v11, 1, v13, v15, v16, v2, v4, v6, v8, 0, 3, 4) -> f_110(v1, v3, v5, v7, v9, v11, 1, v13, v15, v16, v2, v4, v6, v8, 0, 3, 4) :|: 1 + v15 = v9 f_110(v1, v3, v5, v7, v9, v11, 1, v13, v15, v16, v2, v4, v6, v8, 0, 3, 4) -> f_111(v1, v3, v5, v7, v9, v11, 1, v13, v15, v16, v2, v4, v6, v8, 0, 3, 4) :|: 0 = 0 f_111(v1, v3, v5, v7, v9, v11, 1, v13, v15, v16, v2, v4, v6, v8, 0, 3, 4) -> f_112(v1, v3, v5, v7, v9, v11, 1, v13, v15, v18, v2, v4, v6, v8, 0, 3, 4) :|: v18 + v13 = v15 && v16 = v18 f_112(v1, v3, v5, v7, v9, v11, 1, v13, v15, v18, v2, v4, v6, v8, 0, 3, 4) -> f_113(v1, v3, v5, v7, v9, v11, 1, v13, v15, v18, v2, v4, v6, v8, 0, 3, 4) :|: TRUE f_113(v1, v3, v5, v7, v9, v11, 1, v13, v15, v18, v2, v4, v6, v8, 0, 3, 4) -> f_114(v1, v3, v5, v7, v9, v11, 1, v13, v15, v18, v2, v4, v6, v8, 0, 3, 4) :|: TRUE f_114(v1, v3, v5, v7, v9, v11, 1, v13, v15, v18, v2, v4, v6, v8, 0, 3, 4) -> f_135(v1, v3, v5, v7, v9, v11, v11, 1, v13, v9, v15, v18, v2, v4, v6, v8, 0, 3, 4) :|: TRUE Combined rules. Obtained 2 rulesP rules: f_84 -> f_136(v1:0, v3:0, v5:0, v7:0, 1 + (v16:0 + v13:0), v11:0, v16:0, 1, v13:0, 1 + (v16:0 + v13:0), v16:0 + v13:0, 3 + v1:0, 3 + v3:0, 3 + v5:0, 3 + v7:0, 0, 3, 4) :|: v3:0 > 0 && v1:0 > 0 && v5:0 > 0 && v7:0 > 0 && v11:0 > 0 f_136(v27:0, v28:0, v29:0, v30:0, v31:0, v32:0, 1 + (v47:0 + v44:0), 1, v35:0, v36:0, v37:0, v39:0, v40:0, v41:0, v42:0, 0, 3, 4) -> f_136(v27:0, v28:0, v29:0, v30:0, v31:0, v32:0, v47:0, 1, v44:0, 1 + (v47:0 + v44:0), v47:0 + v44:0, v39:0, v40:0, v41:0, v42:0, 0, 3, 4) :|: v47:0 + v44:0 > -1 Filtered unneeded arguments: f_136(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) -> f_136(x7) Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules: f_84 -> f_136(v16:0) :|: TRUE f_136(sum~cons_1~sum~v47:0~v44:0) -> f_136(v47:0) :|: v47:0 + v44:0 > -1 && sum~cons_1~sum~v47:0~v44:0 = 1 + (v47:0 + v44:0) ---------------------------------------- (8) Obligation: Rules: f_84 -> f_136(v16:0) :|: TRUE f_136(sum~cons_1~sum~v47:0~v44:0) -> f_136(v47:0) :|: v47:0 + v44:0 > -1 && sum~cons_1~sum~v47:0~v44:0 = 1 + (v47:0 + v44:0) Start term: f_84 ---------------------------------------- (9) IRS2T2 (EQUIVALENT) Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: (f_84_1,1) (f_136_1,2) ---------------------------------------- (10) Obligation: START: 1; FROM: 1; oldX0 := x0; oldX1 := nondet(); assume(0 = 0); x0 := oldX1; TO: 2; FROM: 2; oldX0 := x0; oldX1 := nondet(); oldX2 := nondet(); assume(oldX1 + oldX2 > -1 && oldX0 = 1 + (oldX1 + oldX2)); x0 := oldX1; TO: 2; ---------------------------------------- (11) T2 (COMPLETE) Found this recurrent set for cutpoint 5: oldX1 == 1 and oldX2 == -1 and x0 == 1 ---------------------------------------- (12) NO