5.31/2.29 YES 5.31/2.30 proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar 5.31/2.30 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.31/2.30 5.31/2.30 5.31/2.30 termination of the given Bare JBC problem could be proven: 5.31/2.30 5.31/2.30 (0) Bare JBC problem 5.31/2.30 (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] 5.31/2.30 (2) JBC problem 5.31/2.30 (3) JBCToGraph [EQUIVALENT, 248 ms] 5.31/2.30 (4) JBCTerminationGraph 5.31/2.30 (5) TerminationGraphToSCCProof [SOUND, 0 ms] 5.31/2.30 (6) JBCTerminationSCC 5.31/2.30 (7) SCCToIRSProof [SOUND, 79 ms] 5.31/2.30 (8) IRSwT 5.31/2.30 (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 5.31/2.30 (10) IRSwT 5.31/2.30 (11) IRSwTTerminationDigraphProof [EQUIVALENT, 21 ms] 5.31/2.30 (12) IRSwT 5.31/2.30 (13) IntTRSCompressionProof [EQUIVALENT, 0 ms] 5.31/2.30 (14) IRSwT 5.31/2.30 (15) TempFilterProof [SOUND, 15 ms] 5.31/2.30 (16) IntTRS 5.31/2.30 (17) PolynomialOrderProcessor [EQUIVALENT, 0 ms] 5.31/2.30 (18) YES 5.31/2.30 5.31/2.30 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (0) 5.31/2.30 Obligation: 5.31/2.30 need to prove termination of the following program: 5.31/2.30 public class Overflow { 5.31/2.30 5.31/2.30 // does not terminate for any value of i 5.31/2.30 public static void overflow(int i) { 5.31/2.30 while(i <= 2147483647) { 5.31/2.30 i++; 5.31/2.30 } 5.31/2.30 } 5.31/2.30 5.31/2.30 public static void main(String[] args) { 5.31/2.30 Random.args = args; 5.31/2.30 overflow(Random.random()); 5.31/2.30 } 5.31/2.30 } 5.31/2.30 5.31/2.30 5.31/2.30 public class Random { 5.31/2.30 static String[] args; 5.31/2.30 static int index = 0; 5.31/2.30 5.31/2.30 public static int random() { 5.31/2.30 String string = args[index]; 5.31/2.30 index++; 5.31/2.30 return string.length(); 5.31/2.30 } 5.31/2.30 } 5.31/2.30 5.31/2.30 5.31/2.30 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (1) BareJBCToJBCProof (EQUIVALENT) 5.31/2.30 initialized classpath 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (2) 5.31/2.30 Obligation: 5.31/2.30 need to prove termination of the following program: 5.31/2.30 public class Overflow { 5.31/2.30 5.31/2.30 // does not terminate for any value of i 5.31/2.30 public static void overflow(int i) { 5.31/2.30 while(i <= 2147483647) { 5.31/2.30 i++; 5.31/2.30 } 5.31/2.30 } 5.31/2.30 5.31/2.30 public static void main(String[] args) { 5.31/2.30 Random.args = args; 5.31/2.30 overflow(Random.random()); 5.31/2.30 } 5.31/2.30 } 5.31/2.30 5.31/2.30 5.31/2.30 public class Random { 5.31/2.30 static String[] args; 5.31/2.30 static int index = 0; 5.31/2.30 5.31/2.30 public static int random() { 5.31/2.30 String string = args[index]; 5.31/2.30 index++; 5.31/2.30 return string.length(); 5.31/2.30 } 5.31/2.30 } 5.31/2.30 5.31/2.30 5.31/2.30 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (3) JBCToGraph (EQUIVALENT) 5.31/2.30 Constructed TerminationGraph. 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (4) 5.31/2.30 Obligation: 5.31/2.30 Termination Graph based on JBC Program: 5.31/2.30 Overflow.main([Ljava/lang/String;)V: Graph of 108 nodes with 1 SCC. 5.31/2.30 5.31/2.30 5.31/2.30 5.31/2.30 5.31/2.30 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (5) TerminationGraphToSCCProof (SOUND) 5.31/2.30 Splitted TerminationGraph to 1 SCCs. 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (6) 5.31/2.30 Obligation: 5.31/2.30 SCC of termination graph based on JBC Program. 5.31/2.30 SCC contains nodes from the following methods: Overflow.main([Ljava/lang/String;)V 5.31/2.30 SCC calls the following helper methods: 5.31/2.30 Performed SCC analyses: 5.31/2.30 *Used field analysis yielded the following read fields: 5.31/2.30 5.31/2.30 *Marker field analysis yielded the following relations that could be markers: 5.31/2.30 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (7) SCCToIRSProof (SOUND) 5.31/2.30 Transformed FIGraph SCCs to intTRSs. Log: 5.31/2.30 Generated rules. Obtained 7 IRulesP rules: 5.31/2.30 f130_0_overflow_ConstantStackPush(EOS(STATIC_130), i17, i17) -> f139_0_overflow_GT(EOS(STATIC_139), i17, i17, 2147483647) :|: TRUE 5.31/2.30 f139_0_overflow_GT(EOS(STATIC_139), i22, i22, matching1) -> f144_0_overflow_GT(EOS(STATIC_144), i22, i22, 2147483647) :|: TRUE && matching1 = 2147483647 5.31/2.30 f144_0_overflow_GT(EOS(STATIC_144), i22, i22, matching1) -> f154_0_overflow_Inc(EOS(STATIC_154), i22) :|: i22 <= 2147483647 && matching1 = 2147483647 5.31/2.30 f154_0_overflow_Inc(EOS(STATIC_154), i22) -> f167_0_overflow_JMP(EOS(STATIC_167), i22 + 1) :|: TRUE 5.31/2.30 f167_0_overflow_JMP(EOS(STATIC_167), i26) -> f206_0_overflow_Load(EOS(STATIC_206), i26) :|: TRUE 5.31/2.30 f206_0_overflow_Load(EOS(STATIC_206), i26) -> f118_0_overflow_Load(EOS(STATIC_118), i26) :|: TRUE 5.31/2.30 f118_0_overflow_Load(EOS(STATIC_118), i17) -> f130_0_overflow_ConstantStackPush(EOS(STATIC_130), i17, i17) :|: TRUE 5.31/2.30 Combined rules. Obtained 1 IRulesP rules: 5.31/2.30 f130_0_overflow_ConstantStackPush(EOS(STATIC_130), i17:0, i17:0) -> f130_0_overflow_ConstantStackPush(EOS(STATIC_130), i17:0 + 1, i17:0 + 1) :|: i17:0 < 2147483648 5.31/2.30 Filtered constant ground arguments: 5.31/2.30 f130_0_overflow_ConstantStackPush(x1, x2, x3) -> f130_0_overflow_ConstantStackPush(x2, x3) 5.31/2.30 EOS(x1) -> EOS 5.31/2.30 Filtered duplicate arguments: 5.31/2.30 f130_0_overflow_ConstantStackPush(x1, x2) -> f130_0_overflow_ConstantStackPush(x2) 5.31/2.30 Finished conversion. Obtained 1 rules.P rules: 5.31/2.30 f130_0_overflow_ConstantStackPush(i17:0) -> f130_0_overflow_ConstantStackPush(i17:0 + 1) :|: i17:0 < 2147483648 5.31/2.30 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (8) 5.31/2.30 Obligation: 5.31/2.30 Rules: 5.31/2.30 f130_0_overflow_ConstantStackPush(i17:0) -> f130_0_overflow_ConstantStackPush(i17:0 + 1) :|: i17:0 < 2147483648 5.31/2.30 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (9) IRSFormatTransformerProof (EQUIVALENT) 5.31/2.30 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (10) 5.31/2.30 Obligation: 5.31/2.30 Rules: 5.31/2.30 f130_0_overflow_ConstantStackPush(i17:0) -> f130_0_overflow_ConstantStackPush(arith) :|: i17:0 < 2147483648 && arith = i17:0 + 1 5.31/2.30 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (11) IRSwTTerminationDigraphProof (EQUIVALENT) 5.31/2.30 Constructed termination digraph! 5.31/2.30 Nodes: 5.31/2.30 (1) f130_0_overflow_ConstantStackPush(i17:0) -> f130_0_overflow_ConstantStackPush(arith) :|: i17:0 < 2147483648 && arith = i17:0 + 1 5.31/2.30 5.31/2.30 Arcs: 5.31/2.30 (1) -> (1) 5.31/2.30 5.31/2.30 This digraph is fully evaluated! 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (12) 5.31/2.30 Obligation: 5.31/2.30 5.31/2.30 Termination digraph: 5.31/2.30 Nodes: 5.31/2.30 (1) f130_0_overflow_ConstantStackPush(i17:0) -> f130_0_overflow_ConstantStackPush(arith) :|: i17:0 < 2147483648 && arith = i17:0 + 1 5.31/2.30 5.31/2.30 Arcs: 5.31/2.30 (1) -> (1) 5.31/2.30 5.31/2.30 This digraph is fully evaluated! 5.31/2.30 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (13) IntTRSCompressionProof (EQUIVALENT) 5.31/2.30 Compressed rules. 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (14) 5.31/2.30 Obligation: 5.31/2.30 Rules: 5.31/2.30 f130_0_overflow_ConstantStackPush(i17:0:0) -> f130_0_overflow_ConstantStackPush(i17:0:0 + 1) :|: i17:0:0 < 2147483648 5.31/2.30 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (15) TempFilterProof (SOUND) 5.31/2.30 Used the following sort dictionary for filtering: 5.31/2.30 f130_0_overflow_ConstantStackPush(INTEGER) 5.31/2.30 Replaced non-predefined constructor symbols by 0. 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (16) 5.31/2.30 Obligation: 5.31/2.30 Rules: 5.31/2.30 f130_0_overflow_ConstantStackPush(i17:0:0) -> f130_0_overflow_ConstantStackPush(c) :|: c = i17:0:0 + 1 && i17:0:0 < 2147483648 5.31/2.30 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (17) PolynomialOrderProcessor (EQUIVALENT) 5.31/2.30 Found the following polynomial interpretation: 5.31/2.30 [f130_0_overflow_ConstantStackPush(x)] = 2147483647 - x 5.31/2.30 5.31/2.30 The following rules are decreasing: 5.31/2.30 f130_0_overflow_ConstantStackPush(i17:0:0) -> f130_0_overflow_ConstantStackPush(c) :|: c = i17:0:0 + 1 && i17:0:0 < 2147483648 5.31/2.30 The following rules are bounded: 5.31/2.30 f130_0_overflow_ConstantStackPush(i17:0:0) -> f130_0_overflow_ConstantStackPush(c) :|: c = i17:0:0 + 1 && i17:0:0 < 2147483648 5.31/2.30 5.31/2.30 ---------------------------------------- 5.31/2.30 5.31/2.30 (18) 5.31/2.30 YES 5.61/2.35 EOF