./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/fermat2-ll_unwindbound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 4f9af400 extending candidate: java ['java'] extending candidate: /usr/bin/java ['java', '/usr/bin/java'] extending candidate: /opt/oracle-jdk-bin-*/bin/java ['java', '/usr/bin/java'] extending candidate: /opt/openjdk-*/bin/java ['java', '/usr/bin/java'] extending candidate: /usr/lib/jvm/java-*-openjdk-amd64/bin/java ['java', '/usr/bin/java', '/usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java', '/usr/lib/jvm/java-17-openjdk-amd64/bin/java', '/usr/lib/jvm/java-11-openjdk-amd64/bin/java', '/usr/lib/jvm/java-1.17.0-openjdk-amd64/bin/java'] ['/root/.sdkman/candidates/java/21.0.5-tem/bin/java', '-Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config', '-Xmx15G', '-Xms4m', '-jar', '/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar', '-data', '@noDefault', '-ultimatedata', '/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data', '-tc', '/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml', '-i', '../sv-benchmarks/c/nla-digbench-scaling/fermat2-ll_unwindbound10.c', '-s', '/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf', '--cacsl2boogietranslator.entry.function', 'main', '--witnessprinter.witness.directory', '/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux', '--witnessprinter.witness.filename', 'witness', '--witnessprinter.write.witness.besides.input.file', 'false', '--witnessprinter.graph.data.specification', 'CHECK( init(main()), LTL(G ! call(reach_error())) )\n\n', '--witnessprinter.graph.data.producer', 'Automizer', '--witnessprinter.graph.data.architecture', '32bit', '--witnessprinter.graph.data.programhash', '96b71e4fe20331af08d1b5394215c6ca1c246124118142d0900823a256b0e31d'] Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/fermat2-ll_unwindbound10.c -s /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 96b71e4fe20331af08d1b5394215c6ca1c246124118142d0900823a256b0e31d --- Real Ultimate output --- This is Ultimate 0.3.0-?-4f9af40 [2024-11-06 22:57:44,996 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-06 22:57:45,059 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-06 22:57:45,063 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-06 22:57:45,063 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-06 22:57:45,086 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-06 22:57:45,088 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-06 22:57:45,088 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-06 22:57:45,088 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-06 22:57:45,088 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-06 22:57:45,088 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-06 22:57:45,088 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-06 22:57:45,088 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-06 22:57:45,089 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-06 22:57:45,089 INFO L153 SettingsManager]: * Use SBE=true [2024-11-06 22:57:45,089 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-06 22:57:45,089 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-06 22:57:45,089 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-06 22:57:45,089 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-06 22:57:45,089 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-06 22:57:45,089 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-06 22:57:45,089 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-06 22:57:45,089 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-06 22:57:45,090 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-06 22:57:45,090 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-06 22:57:45,090 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-06 22:57:45,090 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-06 22:57:45,090 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-06 22:57:45,090 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-06 22:57:45,090 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-06 22:57:45,090 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-06 22:57:45,090 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-06 22:57:45,090 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-06 22:57:45,090 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-06 22:57:45,090 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-06 22:57:45,090 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-06 22:57:45,090 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-06 22:57:45,090 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-06 22:57:45,091 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-06 22:57:45,091 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-06 22:57:45,091 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-06 22:57:45,091 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-06 22:57:45,091 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 96b71e4fe20331af08d1b5394215c6ca1c246124118142d0900823a256b0e31d [2024-11-06 22:57:45,321 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-06 22:57:45,329 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-06 22:57:45,331 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-06 22:57:45,332 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-06 22:57:45,332 INFO L274 PluginConnector]: CDTParser initialized [2024-11-06 22:57:45,333 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/fermat2-ll_unwindbound10.c [2024-11-06 22:57:46,473 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-06 22:57:46,683 INFO L384 CDTParser]: Found 1 translation units. [2024-11-06 22:57:46,684 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/fermat2-ll_unwindbound10.c [2024-11-06 22:57:46,696 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/4f9ac465c/baab5f7fed5f400b818a3f539882952d/FLAGa00cb0b61 [2024-11-06 22:57:47,050 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/4f9ac465c/baab5f7fed5f400b818a3f539882952d [2024-11-06 22:57:47,052 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-06 22:57:47,053 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-06 22:57:47,055 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-06 22:57:47,055 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-06 22:57:47,058 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-06 22:57:47,058 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 10:57:47" (1/1) ... [2024-11-06 22:57:47,059 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@248fdfca and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:57:47, skipping insertion in model container [2024-11-06 22:57:47,059 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 10:57:47" (1/1) ... [2024-11-06 22:57:47,070 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-06 22:57:47,176 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/fermat2-ll_unwindbound10.c[524,537] [2024-11-06 22:57:47,190 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-06 22:57:47,198 INFO L200 MainTranslator]: Completed pre-run [2024-11-06 22:57:47,206 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/fermat2-ll_unwindbound10.c[524,537] [2024-11-06 22:57:47,209 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-06 22:57:47,219 INFO L204 MainTranslator]: Completed translation [2024-11-06 22:57:47,220 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:57:47 WrapperNode [2024-11-06 22:57:47,221 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-06 22:57:47,221 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-06 22:57:47,222 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-06 22:57:47,222 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-06 22:57:47,226 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:57:47" (1/1) ... [2024-11-06 22:57:47,230 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:57:47" (1/1) ... [2024-11-06 22:57:47,243 INFO L138 Inliner]: procedures = 14, calls = 11, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 47 [2024-11-06 22:57:47,243 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-06 22:57:47,244 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-06 22:57:47,244 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-06 22:57:47,244 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-06 22:57:47,249 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:57:47" (1/1) ... [2024-11-06 22:57:47,249 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:57:47" (1/1) ... [2024-11-06 22:57:47,251 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:57:47" (1/1) ... [2024-11-06 22:57:47,263 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-06 22:57:47,264 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:57:47" (1/1) ... [2024-11-06 22:57:47,264 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:57:47" (1/1) ... [2024-11-06 22:57:47,267 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:57:47" (1/1) ... [2024-11-06 22:57:47,269 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:57:47" (1/1) ... [2024-11-06 22:57:47,269 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:57:47" (1/1) ... [2024-11-06 22:57:47,270 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:57:47" (1/1) ... [2024-11-06 22:57:47,274 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-06 22:57:47,275 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-06 22:57:47,275 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-06 22:57:47,275 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-06 22:57:47,276 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:57:47" (1/1) ... [2024-11-06 22:57:47,279 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-06 22:57:47,289 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:57:47,298 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-06 22:57:47,301 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-06 22:57:47,318 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-06 22:57:47,318 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-06 22:57:47,318 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-06 22:57:47,318 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-06 22:57:47,318 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-06 22:57:47,318 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-06 22:57:47,318 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-06 22:57:47,319 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-06 22:57:47,368 INFO L238 CfgBuilder]: Building ICFG [2024-11-06 22:57:47,369 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-06 22:57:47,470 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-06 22:57:47,470 INFO L287 CfgBuilder]: Performing block encoding [2024-11-06 22:57:47,481 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-06 22:57:47,483 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-06 22:57:47,483 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 10:57:47 BoogieIcfgContainer [2024-11-06 22:57:47,483 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-06 22:57:47,486 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-06 22:57:47,486 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-06 22:57:47,490 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-06 22:57:47,491 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.11 10:57:47" (1/3) ... [2024-11-06 22:57:47,491 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2b0f9520 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 10:57:47, skipping insertion in model container [2024-11-06 22:57:47,491 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:57:47" (2/3) ... [2024-11-06 22:57:47,492 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2b0f9520 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 10:57:47, skipping insertion in model container [2024-11-06 22:57:47,492 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 10:57:47" (3/3) ... [2024-11-06 22:57:47,493 INFO L112 eAbstractionObserver]: Analyzing ICFG fermat2-ll_unwindbound10.c [2024-11-06 22:57:47,506 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-06 22:57:47,506 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-06 22:57:47,544 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-06 22:57:47,554 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@42efe4a, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-06 22:57:47,554 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-06 22:57:47,559 INFO L276 IsEmpty]: Start isEmpty. Operand has 25 states, 17 states have (on average 1.411764705882353) internal successors, (24), 18 states have internal predecessors, (24), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-06 22:57:47,564 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-11-06 22:57:47,564 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:57:47,565 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:57:47,565 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:57:47,568 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:57:47,569 INFO L85 PathProgramCache]: Analyzing trace with hash 1086166160, now seen corresponding path program 1 times [2024-11-06 22:57:47,574 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:57:47,574 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [148888767] [2024-11-06 22:57:47,574 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:57:47,575 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:57:47,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:47,672 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:57:47,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:47,683 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-06 22:57:47,687 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:47,696 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 22:57:47,697 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:57:47,698 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [148888767] [2024-11-06 22:57:47,699 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [148888767] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:57:47,699 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:57:47,700 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-06 22:57:47,701 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [976563723] [2024-11-06 22:57:47,701 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:57:47,704 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-06 22:57:47,705 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:57:47,721 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-06 22:57:47,721 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-06 22:57:47,723 INFO L87 Difference]: Start difference. First operand has 25 states, 17 states have (on average 1.411764705882353) internal successors, (24), 18 states have internal predecessors, (24), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-06 22:57:47,737 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:57:47,738 INFO L93 Difference]: Finished difference Result 47 states and 64 transitions. [2024-11-06 22:57:47,739 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-06 22:57:47,740 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2024-11-06 22:57:47,740 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:57:47,744 INFO L225 Difference]: With dead ends: 47 [2024-11-06 22:57:47,745 INFO L226 Difference]: Without dead ends: 21 [2024-11-06 22:57:47,747 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-06 22:57:47,750 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 29 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:57:47,751 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:57:47,760 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2024-11-06 22:57:47,771 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2024-11-06 22:57:47,772 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 15 states have internal predecessors, (18), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-06 22:57:47,775 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 25 transitions. [2024-11-06 22:57:47,777 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 25 transitions. Word has length 18 [2024-11-06 22:57:47,777 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:57:47,777 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 25 transitions. [2024-11-06 22:57:47,777 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-06 22:57:47,777 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 25 transitions. [2024-11-06 22:57:47,778 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-06 22:57:47,778 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:57:47,778 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:57:47,780 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-06 22:57:47,780 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:57:47,780 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:57:47,781 INFO L85 PathProgramCache]: Analyzing trace with hash 1345709874, now seen corresponding path program 1 times [2024-11-06 22:57:47,781 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:57:47,781 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1793327143] [2024-11-06 22:57:47,781 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:57:47,782 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:57:47,809 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:47,909 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:57:47,911 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:47,917 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-06 22:57:47,922 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:47,930 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 22:57:47,930 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:57:47,930 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1793327143] [2024-11-06 22:57:47,930 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1793327143] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:57:47,930 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:57:47,930 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-06 22:57:47,930 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [760413898] [2024-11-06 22:57:47,930 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:57:47,931 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-06 22:57:47,931 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:57:47,932 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-06 22:57:47,932 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-06 22:57:47,932 INFO L87 Difference]: Start difference. First operand 21 states and 25 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-06 22:57:47,953 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:57:47,953 INFO L93 Difference]: Finished difference Result 30 states and 34 transitions. [2024-11-06 22:57:47,953 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-06 22:57:47,954 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2024-11-06 22:57:47,954 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:57:47,954 INFO L225 Difference]: With dead ends: 30 [2024-11-06 22:57:47,955 INFO L226 Difference]: Without dead ends: 23 [2024-11-06 22:57:47,955 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-06 22:57:47,956 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 5 mSDsluCounter, 34 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 57 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:57:47,956 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 57 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:57:47,957 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2024-11-06 22:57:47,959 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2024-11-06 22:57:47,959 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-06 22:57:47,959 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 27 transitions. [2024-11-06 22:57:47,960 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 27 transitions. Word has length 19 [2024-11-06 22:57:47,960 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:57:47,960 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 27 transitions. [2024-11-06 22:57:47,961 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-06 22:57:47,961 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 27 transitions. [2024-11-06 22:57:47,961 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-06 22:57:47,961 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:57:47,961 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:57:47,961 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-06 22:57:47,961 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:57:47,962 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:57:47,962 INFO L85 PathProgramCache]: Analyzing trace with hash 1347497334, now seen corresponding path program 1 times [2024-11-06 22:57:47,962 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:57:47,962 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [461970279] [2024-11-06 22:57:47,962 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:57:47,962 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:57:47,994 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:57:47,996 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [778074609] [2024-11-06 22:57:47,998 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:57:47,998 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:57:47,999 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:57:48,000 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:57:48,002 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-06 22:57:48,059 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:48,062 INFO L255 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-06 22:57:48,067 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:57:48,236 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 22:57:48,236 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 22:57:48,236 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:57:48,237 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [461970279] [2024-11-06 22:57:48,237 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:57:48,237 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [778074609] [2024-11-06 22:57:48,237 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [778074609] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:57:48,237 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:57:48,237 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:57:48,238 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [753957165] [2024-11-06 22:57:48,238 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:57:48,238 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:57:48,238 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:57:48,239 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:57:48,240 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:57:48,240 INFO L87 Difference]: Start difference. First operand 23 states and 27 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-06 22:57:48,714 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:57:48,714 INFO L93 Difference]: Finished difference Result 35 states and 42 transitions. [2024-11-06 22:57:48,714 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:57:48,714 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2024-11-06 22:57:48,714 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:57:48,715 INFO L225 Difference]: With dead ends: 35 [2024-11-06 22:57:48,715 INFO L226 Difference]: Without dead ends: 33 [2024-11-06 22:57:48,715 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-06 22:57:48,715 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 5 mSDsluCounter, 55 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-06 22:57:48,716 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 75 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-06 22:57:48,716 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2024-11-06 22:57:48,721 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 32. [2024-11-06 22:57:48,722 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-06 22:57:48,723 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 39 transitions. [2024-11-06 22:57:48,723 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 39 transitions. Word has length 19 [2024-11-06 22:57:48,723 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:57:48,723 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 39 transitions. [2024-11-06 22:57:48,724 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-06 22:57:48,724 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 39 transitions. [2024-11-06 22:57:48,724 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-06 22:57:48,725 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:57:48,725 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:57:48,738 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-06 22:57:48,929 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:57:48,930 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:57:48,930 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:57:48,930 INFO L85 PathProgramCache]: Analyzing trace with hash 1636478750, now seen corresponding path program 1 times [2024-11-06 22:57:48,930 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:57:48,930 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [320965212] [2024-11-06 22:57:48,930 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:57:48,930 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:57:48,953 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:49,127 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:57:49,128 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:49,130 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-06 22:57:49,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:49,136 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-06 22:57:49,138 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:49,166 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 22:57:49,166 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:57:49,166 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [320965212] [2024-11-06 22:57:49,166 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [320965212] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:57:49,166 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [692326445] [2024-11-06 22:57:49,166 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:57:49,167 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:57:49,167 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:57:49,169 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:57:49,170 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-06 22:57:49,203 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:49,204 INFO L255 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-06 22:57:49,205 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:57:49,262 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 22:57:49,262 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:57:49,355 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 22:57:49,356 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [692326445] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:57:49,356 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-06 22:57:49,356 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8, 8] total 12 [2024-11-06 22:57:49,356 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [516003497] [2024-11-06 22:57:49,356 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-06 22:57:49,356 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-06 22:57:49,356 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:57:49,357 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-06 22:57:49,357 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2024-11-06 22:57:49,357 INFO L87 Difference]: Start difference. First operand 32 states and 39 transitions. Second operand has 12 states, 11 states have (on average 1.9090909090909092) internal successors, (21), 8 states have internal predecessors, (21), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (5), 4 states have call predecessors, (5), 1 states have call successors, (5) [2024-11-06 22:57:49,432 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:57:49,432 INFO L93 Difference]: Finished difference Result 39 states and 45 transitions. [2024-11-06 22:57:49,433 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-06 22:57:49,433 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 1.9090909090909092) internal successors, (21), 8 states have internal predecessors, (21), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (5), 4 states have call predecessors, (5), 1 states have call successors, (5) Word has length 25 [2024-11-06 22:57:49,433 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:57:49,434 INFO L225 Difference]: With dead ends: 39 [2024-11-06 22:57:49,434 INFO L226 Difference]: Without dead ends: 34 [2024-11-06 22:57:49,434 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 50 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2024-11-06 22:57:49,434 INFO L432 NwaCegarLoop]: 18 mSDtfsCounter, 8 mSDsluCounter, 77 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:57:49,434 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 95 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:57:49,435 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2024-11-06 22:57:49,439 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 25. [2024-11-06 22:57:49,439 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 18 states have (on average 1.1111111111111112) internal successors, (20), 18 states have internal predecessors, (20), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-06 22:57:49,439 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 27 transitions. [2024-11-06 22:57:49,440 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 27 transitions. Word has length 25 [2024-11-06 22:57:49,440 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:57:49,440 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 27 transitions. [2024-11-06 22:57:49,440 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 1.9090909090909092) internal successors, (21), 8 states have internal predecessors, (21), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (5), 4 states have call predecessors, (5), 1 states have call successors, (5) [2024-11-06 22:57:49,440 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 27 transitions. [2024-11-06 22:57:49,441 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-06 22:57:49,442 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:57:49,442 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:57:49,454 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-06 22:57:49,643 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:57:49,643 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:57:49,643 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:57:49,643 INFO L85 PathProgramCache]: Analyzing trace with hash -126969667, now seen corresponding path program 1 times [2024-11-06 22:57:49,643 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:57:49,643 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [558249636] [2024-11-06 22:57:49,644 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:57:49,644 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:57:49,651 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:49,697 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:57:49,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:49,703 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-06 22:57:49,705 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:49,709 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-06 22:57:49,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:49,715 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 22:57:49,717 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:57:49,717 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [558249636] [2024-11-06 22:57:49,717 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [558249636] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:57:49,717 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [512907570] [2024-11-06 22:57:49,717 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:57:49,717 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:57:49,718 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:57:49,719 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:57:49,720 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-06 22:57:49,755 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:49,760 INFO L255 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-06 22:57:49,761 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:57:49,794 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 22:57:49,794 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:57:49,845 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 22:57:49,846 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [512907570] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:57:49,846 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-06 22:57:49,846 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 5] total 8 [2024-11-06 22:57:49,846 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [780999593] [2024-11-06 22:57:49,846 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-06 22:57:49,846 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-06 22:57:49,846 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:57:49,847 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-06 22:57:49,847 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2024-11-06 22:57:49,847 INFO L87 Difference]: Start difference. First operand 25 states and 27 transitions. Second operand has 8 states, 8 states have (on average 4.125) internal successors, (33), 8 states have internal predecessors, (33), 5 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-06 22:57:49,912 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:57:49,912 INFO L93 Difference]: Finished difference Result 57 states and 64 transitions. [2024-11-06 22:57:49,913 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-06 22:57:49,913 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.125) internal successors, (33), 8 states have internal predecessors, (33), 5 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 28 [2024-11-06 22:57:49,913 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:57:49,914 INFO L225 Difference]: With dead ends: 57 [2024-11-06 22:57:49,914 INFO L226 Difference]: Without dead ends: 52 [2024-11-06 22:57:49,914 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 58 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2024-11-06 22:57:49,914 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 16 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:57:49,914 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 96 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:57:49,915 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2024-11-06 22:57:49,927 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2024-11-06 22:57:49,928 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 39 states have (on average 1.1282051282051282) internal successors, (44), 39 states have internal predecessors, (44), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-06 22:57:49,928 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 57 transitions. [2024-11-06 22:57:49,930 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 57 transitions. Word has length 28 [2024-11-06 22:57:49,930 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:57:49,930 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 57 transitions. [2024-11-06 22:57:49,930 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.125) internal successors, (33), 8 states have internal predecessors, (33), 5 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-06 22:57:49,930 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 57 transitions. [2024-11-06 22:57:49,931 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2024-11-06 22:57:49,931 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:57:49,931 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:57:49,946 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-06 22:57:50,131 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:57:50,132 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:57:50,132 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:57:50,132 INFO L85 PathProgramCache]: Analyzing trace with hash 972990450, now seen corresponding path program 2 times [2024-11-06 22:57:50,132 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:57:50,132 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [775169005] [2024-11-06 22:57:50,132 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:57:50,133 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:57:50,144 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:50,275 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:57:50,277 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:50,283 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-06 22:57:50,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:50,287 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-06 22:57:50,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:50,290 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-06 22:57:50,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:50,293 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-11-06 22:57:50,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:50,296 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-06 22:57:50,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:57:50,299 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 8 proven. 38 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-06 22:57:50,299 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:57:50,299 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [775169005] [2024-11-06 22:57:50,299 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [775169005] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:57:50,299 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [438099557] [2024-11-06 22:57:50,300 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-06 22:57:50,300 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:57:50,300 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:57:50,302 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:57:50,303 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-06 22:57:50,375 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-06 22:57:50,375 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-06 22:57:50,376 INFO L255 TraceCheckSpWp]: Trace formula consists of 145 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-06 22:57:50,377 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:57:50,450 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 8 proven. 62 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 22:57:50,450 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:57:50,555 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 8 proven. 38 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-06 22:57:50,556 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [438099557] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:57:50,556 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-06 22:57:50,557 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 8] total 14 [2024-11-06 22:57:50,557 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [386038596] [2024-11-06 22:57:50,557 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-06 22:57:50,557 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-06 22:57:50,557 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:57:50,558 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-06 22:57:50,558 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2024-11-06 22:57:50,558 INFO L87 Difference]: Start difference. First operand 52 states and 57 transitions. Second operand has 14 states, 14 states have (on average 4.714285714285714) internal successors, (66), 14 states have internal predecessors, (66), 11 states have call successors, (19), 7 states have call predecessors, (19), 6 states have return successors, (18), 10 states have call predecessors, (18), 10 states have call successors, (18) [2024-11-06 22:57:50,725 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:57:50,725 INFO L93 Difference]: Finished difference Result 111 states and 127 transitions. [2024-11-06 22:57:50,725 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-06 22:57:50,726 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.714285714285714) internal successors, (66), 14 states have internal predecessors, (66), 11 states have call successors, (19), 7 states have call predecessors, (19), 6 states have return successors, (18), 10 states have call predecessors, (18), 10 states have call successors, (18) Word has length 55 [2024-11-06 22:57:50,726 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:57:50,727 INFO L225 Difference]: With dead ends: 111 [2024-11-06 22:57:50,727 INFO L226 Difference]: Without dead ends: 106 [2024-11-06 22:57:50,727 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 136 GetRequests, 115 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2024-11-06 22:57:50,727 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 56 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:57:50,728 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 112 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:57:50,728 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2024-11-06 22:57:50,750 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 106. [2024-11-06 22:57:50,751 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 81 states have (on average 1.1358024691358024) internal successors, (92), 81 states have internal predecessors, (92), 13 states have call successors, (13), 12 states have call predecessors, (13), 11 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-06 22:57:50,752 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 117 transitions. [2024-11-06 22:57:50,752 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 117 transitions. Word has length 55 [2024-11-06 22:57:50,752 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:57:50,752 INFO L471 AbstractCegarLoop]: Abstraction has 106 states and 117 transitions. [2024-11-06 22:57:50,752 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.714285714285714) internal successors, (66), 14 states have internal predecessors, (66), 11 states have call successors, (19), 7 states have call predecessors, (19), 6 states have return successors, (18), 10 states have call predecessors, (18), 10 states have call successors, (18) [2024-11-06 22:57:50,752 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 117 transitions. [2024-11-06 22:57:50,755 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 110 [2024-11-06 22:57:50,756 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:57:50,757 INFO L215 NwaCegarLoop]: trace histogram [11, 11, 10, 10, 10, 10, 10, 10, 10, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:57:50,763 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-06 22:57:50,960 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2024-11-06 22:57:50,961 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:57:50,961 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:57:50,961 INFO L85 PathProgramCache]: Analyzing trace with hash -1909967598, now seen corresponding path program 3 times [2024-11-06 22:57:50,961 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:57:50,961 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [221768132] [2024-11-06 22:57:50,961 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:57:50,961 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:57:51,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:57:51,012 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1478166584] [2024-11-06 22:57:51,012 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-06 22:57:51,012 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:57:51,012 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:57:51,014 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:57:51,016 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-06 22:57:51,150 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2024-11-06 22:57:51,150 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-06 22:57:51,151 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-06 22:57:51,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-06 22:57:51,210 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-06 22:57:51,210 INFO L325 BasicCegarLoop]: Counterexample is feasible [2024-11-06 22:57:51,211 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-06 22:57:51,219 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-06 22:57:51,413 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:57:51,415 INFO L407 BasicCegarLoop]: Path program histogram: [3, 1, 1, 1, 1] [2024-11-06 22:57:51,444 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-06 22:57:51,446 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.11 10:57:51 BoogieIcfgContainer [2024-11-06 22:57:51,447 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-06 22:57:51,447 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-06 22:57:51,447 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-06 22:57:51,447 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-06 22:57:51,448 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 10:57:47" (3/4) ... [2024-11-06 22:57:51,448 INFO L136 WitnessPrinter]: Generating witness for reachability counterexample [2024-11-06 22:57:51,491 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-11-06 22:57:51,491 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-06 22:57:51,492 INFO L158 Benchmark]: Toolchain (without parser) took 4438.40ms. Allocated memory is still 142.6MB. Free memory was 117.7MB in the beginning and 49.4MB in the end (delta: 68.3MB). Peak memory consumption was 63.3MB. Max. memory is 16.1GB. [2024-11-06 22:57:51,493 INFO L158 Benchmark]: CDTParser took 0.22ms. Allocated memory is still 117.4MB. Free memory is still 81.2MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-06 22:57:51,493 INFO L158 Benchmark]: CACSL2BoogieTranslator took 166.42ms. Allocated memory is still 142.6MB. Free memory was 117.5MB in the beginning and 106.5MB in the end (delta: 11.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-06 22:57:51,493 INFO L158 Benchmark]: Boogie Procedure Inliner took 22.08ms. Allocated memory is still 142.6MB. Free memory was 106.5MB in the beginning and 105.4MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-06 22:57:51,493 INFO L158 Benchmark]: Boogie Preprocessor took 30.44ms. Allocated memory is still 142.6MB. Free memory was 105.2MB in the beginning and 104.1MB in the end (delta: 1.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-06 22:57:51,494 INFO L158 Benchmark]: RCFGBuilder took 208.73ms. Allocated memory is still 142.6MB. Free memory was 104.1MB in the beginning and 93.3MB in the end (delta: 10.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-06 22:57:51,494 INFO L158 Benchmark]: TraceAbstraction took 3960.55ms. Allocated memory is still 142.6MB. Free memory was 92.8MB in the beginning and 53.1MB in the end (delta: 39.7MB). Peak memory consumption was 38.1MB. Max. memory is 16.1GB. [2024-11-06 22:57:51,494 INFO L158 Benchmark]: Witness Printer took 44.06ms. Allocated memory is still 142.6MB. Free memory was 53.1MB in the beginning and 49.4MB in the end (delta: 3.7MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-06 22:57:51,496 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.22ms. Allocated memory is still 117.4MB. Free memory is still 81.2MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 166.42ms. Allocated memory is still 142.6MB. Free memory was 117.5MB in the beginning and 106.5MB in the end (delta: 11.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 22.08ms. Allocated memory is still 142.6MB. Free memory was 106.5MB in the beginning and 105.4MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 30.44ms. Allocated memory is still 142.6MB. Free memory was 105.2MB in the beginning and 104.1MB in the end (delta: 1.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * RCFGBuilder took 208.73ms. Allocated memory is still 142.6MB. Free memory was 104.1MB in the beginning and 93.3MB in the end (delta: 10.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 3960.55ms. Allocated memory is still 142.6MB. Free memory was 92.8MB in the beginning and 53.1MB in the end (delta: 39.7MB). Peak memory consumption was 38.1MB. Max. memory is 16.1GB. * Witness Printer took 44.06ms. Allocated memory is still 142.6MB. Free memory was 53.1MB in the beginning and 49.4MB in the end (delta: 3.7MB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 14]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L19] int counter = 0; VAL [counter=0] [L21] int A, R; [L22] long long u, v, r; [L23] A = __VERIFIER_nondet_int() [L24] R = __VERIFIER_nondet_int() [L26] CALL assume_abort_if_not(((long long) R - 1) * ((long long) R - 1) < A) VAL [\old(cond)=1, counter=0] [L9] COND FALSE !(!cond) VAL [\old(cond)=1, counter=0] [L26] RET assume_abort_if_not(((long long) R - 1) * ((long long) R - 1) < A) VAL [A=2603, R=52, counter=0] [L28] CALL assume_abort_if_not(A % 2 == 1) VAL [\old(cond)=1, counter=0] [L9] COND FALSE !(!cond) VAL [\old(cond)=1, counter=0] [L28] RET assume_abort_if_not(A % 2 == 1) VAL [A=2603, R=52, counter=0] [L30] u = ((long long) 2 * R) + 1 [L31] v = 1 [L32] r = ((long long) R * R) - A VAL [A=2603, counter=0, r=101, u=105, v=1] [L34] EXPR counter++ VAL [A=2603, counter=1, r=101, u=105, v=1] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [\old(cond)=1, counter=1] [L12] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L35] RET __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [A=2603, counter=1, r=101, u=105, v=1] [L36] COND FALSE !(!(r != 0)) VAL [A=2603, counter=1, r=101, u=105, v=1] [L38] COND TRUE r > 0 [L39] r = r - v [L40] v = v + 2 VAL [A=2603, counter=1, r=100, u=105, v=3] [L34] EXPR counter++ VAL [A=2603, counter=2, r=100, u=105, v=3] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [\old(cond)=1, counter=2] [L12] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L35] RET __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [A=2603, counter=2, r=100, u=105, v=3] [L36] COND FALSE !(!(r != 0)) VAL [A=2603, counter=2, r=100, u=105, v=3] [L38] COND TRUE r > 0 [L39] r = r - v [L40] v = v + 2 VAL [A=2603, counter=2, r=97, u=105, v=5] [L34] EXPR counter++ VAL [A=2603, counter=3, r=97, u=105, v=5] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [\old(cond)=1, counter=3] [L12] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=3] [L35] RET __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [A=2603, counter=3, r=97, u=105, v=5] [L36] COND FALSE !(!(r != 0)) VAL [A=2603, counter=3, r=97, u=105, v=5] [L38] COND TRUE r > 0 [L39] r = r - v [L40] v = v + 2 VAL [A=2603, counter=3, r=92, u=105, v=7] [L34] EXPR counter++ VAL [A=2603, counter=4, r=92, u=105, v=7] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [\old(cond)=1, counter=4] [L12] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L35] RET __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [A=2603, counter=4, r=92, u=105, v=7] [L36] COND FALSE !(!(r != 0)) VAL [A=2603, counter=4, r=92, u=105, v=7] [L38] COND TRUE r > 0 [L39] r = r - v [L40] v = v + 2 VAL [A=2603, counter=4, r=85, u=105, v=9] [L34] EXPR counter++ VAL [A=2603, counter=5, r=85, u=105, v=9] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [\old(cond)=1, counter=5] [L12] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L35] RET __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [A=2603, counter=5, r=85, u=105, v=9] [L36] COND FALSE !(!(r != 0)) VAL [A=2603, counter=5, r=85, u=105, v=9] [L38] COND TRUE r > 0 [L39] r = r - v [L40] v = v + 2 VAL [A=2603, counter=5, r=76, u=105, v=11] [L34] EXPR counter++ VAL [A=2603, counter=6, r=76, u=105, v=11] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [\old(cond)=1, counter=6] [L12] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=6] [L35] RET __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [A=2603, counter=6, r=76, u=105, v=11] [L36] COND FALSE !(!(r != 0)) VAL [A=2603, counter=6, r=76, u=105, v=11] [L38] COND TRUE r > 0 [L39] r = r - v [L40] v = v + 2 VAL [A=2603, counter=6, r=65, u=105, v=13] [L34] EXPR counter++ VAL [A=2603, counter=7, r=65, u=105, v=13] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [\old(cond)=1, counter=7] [L12] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=7] [L35] RET __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [A=2603, counter=7, r=65, u=105, v=13] [L36] COND FALSE !(!(r != 0)) VAL [A=2603, counter=7, r=65, u=105, v=13] [L38] COND TRUE r > 0 [L39] r = r - v [L40] v = v + 2 VAL [A=2603, counter=7, r=52, u=105, v=15] [L34] EXPR counter++ VAL [A=2603, counter=8, r=52, u=105, v=15] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [\old(cond)=1, counter=8] [L12] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=8] [L35] RET __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [A=2603, counter=8, r=52, u=105, v=15] [L36] COND FALSE !(!(r != 0)) VAL [A=2603, counter=8, r=52, u=105, v=15] [L38] COND TRUE r > 0 [L39] r = r - v [L40] v = v + 2 VAL [A=2603, counter=8, r=37, u=105, v=17] [L34] EXPR counter++ VAL [A=2603, counter=9, r=37, u=105, v=17] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [\old(cond)=1, counter=9] [L12] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=9] [L35] RET __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [A=2603, counter=9, r=37, u=105, v=17] [L36] COND FALSE !(!(r != 0)) VAL [A=2603, counter=9, r=37, u=105, v=17] [L38] COND TRUE r > 0 [L39] r = r - v [L40] v = v + 2 VAL [A=2603, counter=9, r=20, u=105, v=19] [L34] EXPR counter++ VAL [A=2603, counter=10, r=20, u=105, v=19] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [\old(cond)=1, counter=10] [L12] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=10] [L35] RET __VERIFIER_assert(4*(A+r) == u*u - v*v - 2*u + 2*v) VAL [A=2603, counter=10, r=20, u=105, v=19] [L36] COND FALSE !(!(r != 0)) VAL [A=2603, counter=10, r=20, u=105, v=19] [L38] COND TRUE r > 0 [L39] r = r - v [L40] v = v + 2 VAL [A=2603, counter=10, r=1, u=105, v=21] [L34] EXPR counter++ VAL [A=2603, counter=11, r=1, u=105, v=21] [L34] COND FALSE !(counter++<10) [L48] CALL __VERIFIER_assert(((long long) 4*A) == u*u - v*v - 2*u + 2*v) VAL [\old(cond)=0, counter=11] [L12] COND TRUE !(cond) VAL [\old(cond)=0, counter=11] [L14] reach_error() VAL [\old(cond)=0, counter=11] - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 25 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 3.9s, OverallIterations: 7, TraceHistogramMax: 11, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 0.9s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 91 SdHoareTripleChecker+Valid, 0.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 90 mSDsluCounter, 464 SdHoareTripleChecker+Invalid, 0.6s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 330 mSDsCounter, 12 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 157 IncrementalHoareTripleChecker+Invalid, 169 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 12 mSolverCounterUnsat, 134 mSDtfsCounter, 157 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 300 GetRequests, 251 SyntacticMatches, 2 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 90 ImplicationChecksByTransitivity, 0.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=106occurred in iteration=6, InterpolantAutomatonStates: 51, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 6 MinimizatonAttempts, 10 StatesRemovedByMinimization, 2 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 1.2s InterpolantComputationTime, 509 NumberOfCodeBlocks, 509 NumberOfCodeBlocksAsserted, 23 NumberOfCheckSat, 368 ConstructedInterpolants, 0 QuantifiedInterpolants, 985 SizeOfPredicates, 7 NumberOfNonLiveVariables, 371 ConjunctsInSsa, 35 ConjunctsInUnsatCore, 12 InterpolantComputations, 3 PerfectInterpolantSequences, 129/276 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2024-11-06 22:57:51,511 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE