./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/heap-manipulation/bubble_sort_linux-1.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 9bd2c7ff Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/config/AutomizerReach.xml -i ../../sv-benchmarks/c/heap-manipulation/bubble_sort_linux-1.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu --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 a38de44f112a10364737c35b840e673503a211a020b9f494a50e4a32c8fe31c0 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-9bd2c7f [2023-11-19 07:59:17,957 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-19 07:59:18,087 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/config/svcomp-Reach-32bit-Automizer_Default.epf [2023-11-19 07:59:18,092 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-19 07:59:18,093 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-19 07:59:18,126 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-19 07:59:18,128 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-19 07:59:18,129 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-19 07:59:18,130 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-19 07:59:18,136 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-19 07:59:18,137 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-11-19 07:59:18,138 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-11-19 07:59:18,139 INFO L153 SettingsManager]: * Use SBE=true [2023-11-19 07:59:18,140 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-19 07:59:18,140 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-19 07:59:18,141 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-19 07:59:18,141 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-19 07:59:18,142 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-19 07:59:18,142 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-19 07:59:18,143 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-19 07:59:18,144 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-19 07:59:18,144 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-19 07:59:18,145 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-19 07:59:18,146 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-19 07:59:18,146 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-19 07:59:18,147 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-19 07:59:18,148 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-11-19 07:59:18,148 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-19 07:59:18,149 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 07:59:18,149 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-19 07:59:18,151 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-19 07:59:18,151 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-19 07:59:18,152 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-11-19 07:59:18,152 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-19 07:59:18,152 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-11-19 07:59:18,153 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-19 07:59:18,153 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-11-19 07:59:18,153 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-19 07:59:18,154 INFO L153 SettingsManager]: * Independence relation used for large block encoding in concurrent analysis=SYNTACTIC [2023-11-19 07:59:18,154 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release 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 -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu 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 -> a38de44f112a10364737c35b840e673503a211a020b9f494a50e4a32c8fe31c0 [2023-11-19 07:59:18,536 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-19 07:59:18,580 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-19 07:59:18,584 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-19 07:59:18,586 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-19 07:59:18,586 INFO L274 PluginConnector]: CDTParser initialized [2023-11-19 07:59:18,588 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/../../sv-benchmarks/c/heap-manipulation/bubble_sort_linux-1.i [2023-11-19 07:59:21,725 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-19 07:59:22,079 INFO L384 CDTParser]: Found 1 translation units. [2023-11-19 07:59:22,079 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/sv-benchmarks/c/heap-manipulation/bubble_sort_linux-1.i [2023-11-19 07:59:22,101 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/data/e2cc1a59d/1acdab3a4ba64633ba4cf399533f2d03/FLAGa2d03699e [2023-11-19 07:59:22,118 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/data/e2cc1a59d/1acdab3a4ba64633ba4cf399533f2d03 [2023-11-19 07:59:22,121 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-19 07:59:22,123 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-19 07:59:22,124 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-19 07:59:22,124 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-19 07:59:22,130 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-19 07:59:22,131 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 07:59:22" (1/1) ... [2023-11-19 07:59:22,133 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@31e89e15 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 07:59:22, skipping insertion in model container [2023-11-19 07:59:22,133 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 07:59:22" (1/1) ... [2023-11-19 07:59:22,195 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-19 07:59:22,658 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/sv-benchmarks/c/heap-manipulation/bubble_sort_linux-1.i[33822,33835] [2023-11-19 07:59:22,739 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 07:59:22,754 INFO L202 MainTranslator]: Completed pre-run [2023-11-19 07:59:22,829 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/sv-benchmarks/c/heap-manipulation/bubble_sort_linux-1.i[33822,33835] [2023-11-19 07:59:22,854 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 07:59:22,941 INFO L206 MainTranslator]: Completed translation [2023-11-19 07:59:22,941 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 07:59:22 WrapperNode [2023-11-19 07:59:22,941 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-19 07:59:22,944 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-19 07:59:22,944 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-19 07:59:22,944 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-19 07:59:22,954 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 07:59:22" (1/1) ... [2023-11-19 07:59:22,993 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 07:59:22" (1/1) ... [2023-11-19 07:59:23,044 INFO L138 Inliner]: procedures = 232, calls = 75, calls flagged for inlining = 10, calls inlined = 10, statements flattened = 118 [2023-11-19 07:59:23,046 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-19 07:59:23,046 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-19 07:59:23,048 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-19 07:59:23,048 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-19 07:59:23,058 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 07:59:22" (1/1) ... [2023-11-19 07:59:23,059 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 07:59:22" (1/1) ... [2023-11-19 07:59:23,070 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 07:59:22" (1/1) ... [2023-11-19 07:59:23,071 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 07:59:22" (1/1) ... [2023-11-19 07:59:23,085 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 07:59:22" (1/1) ... [2023-11-19 07:59:23,094 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 07:59:22" (1/1) ... [2023-11-19 07:59:23,097 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 07:59:22" (1/1) ... [2023-11-19 07:59:23,100 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 07:59:22" (1/1) ... [2023-11-19 07:59:23,105 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-19 07:59:23,106 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-19 07:59:23,106 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-19 07:59:23,107 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-19 07:59:23,107 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 07:59:22" (1/1) ... [2023-11-19 07:59:23,128 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 07:59:23,150 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/z3 [2023-11-19 07:59:23,175 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-19 07:59:23,198 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-19 07:59:23,229 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2023-11-19 07:59:23,230 INFO L130 BoogieDeclarations]: Found specification of procedure inspect [2023-11-19 07:59:23,230 INFO L138 BoogieDeclarations]: Found implementation of procedure inspect [2023-11-19 07:59:23,231 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-11-19 07:59:23,231 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2023-11-19 07:59:23,231 INFO L130 BoogieDeclarations]: Found specification of procedure val_from_node [2023-11-19 07:59:23,231 INFO L138 BoogieDeclarations]: Found implementation of procedure val_from_node [2023-11-19 07:59:23,232 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-11-19 07:59:23,232 INFO L130 BoogieDeclarations]: Found specification of procedure fail [2023-11-19 07:59:23,232 INFO L138 BoogieDeclarations]: Found implementation of procedure fail [2023-11-19 07:59:23,232 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-11-19 07:59:23,232 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2023-11-19 07:59:23,233 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-19 07:59:23,235 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2023-11-19 07:59:23,236 INFO L130 BoogieDeclarations]: Found specification of procedure list_add [2023-11-19 07:59:23,236 INFO L138 BoogieDeclarations]: Found implementation of procedure list_add [2023-11-19 07:59:23,236 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-19 07:59:23,236 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-19 07:59:23,237 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-19 07:59:23,396 INFO L236 CfgBuilder]: Building ICFG [2023-11-19 07:59:23,399 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-19 07:59:23,877 INFO L277 CfgBuilder]: Performing block encoding [2023-11-19 07:59:23,899 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-19 07:59:23,899 INFO L302 CfgBuilder]: Removed 41 assume(true) statements. [2023-11-19 07:59:23,905 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 07:59:23 BoogieIcfgContainer [2023-11-19 07:59:23,905 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-19 07:59:23,908 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-19 07:59:23,909 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-19 07:59:23,912 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-19 07:59:23,913 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 07:59:22" (1/3) ... [2023-11-19 07:59:23,914 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4a4a0699 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 07:59:23, skipping insertion in model container [2023-11-19 07:59:23,914 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 07:59:22" (2/3) ... [2023-11-19 07:59:23,914 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4a4a0699 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 07:59:23, skipping insertion in model container [2023-11-19 07:59:23,914 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 07:59:23" (3/3) ... [2023-11-19 07:59:23,916 INFO L112 eAbstractionObserver]: Analyzing ICFG bubble_sort_linux-1.i [2023-11-19 07:59:23,938 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-19 07:59:23,938 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-19 07:59:24,001 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-19 07:59:24,008 INFO L357 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, mHoare=true, 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;@4da115fc, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-11-19 07:59:24,009 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-19 07:59:24,014 INFO L276 IsEmpty]: Start isEmpty. Operand has 118 states, 89 states have (on average 1.7415730337078652) internal successors, (155), 108 states have internal predecessors, (155), 23 states have call successors, (23), 4 states have call predecessors, (23), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2023-11-19 07:59:24,023 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-11-19 07:59:24,023 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 07:59:24,024 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 07:59:24,025 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 07:59:24,031 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 07:59:24,032 INFO L85 PathProgramCache]: Analyzing trace with hash 1761516263, now seen corresponding path program 1 times [2023-11-19 07:59:24,043 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-19 07:59:24,043 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [319090007] [2023-11-19 07:59:24,044 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 07:59:24,044 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 07:59:24,152 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:24,260 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 07:59:24,260 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-19 07:59:24,261 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [319090007] [2023-11-19 07:59:24,262 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [319090007] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 07:59:24,262 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 07:59:24,262 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-19 07:59:24,264 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [748116829] [2023-11-19 07:59:24,267 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 07:59:24,272 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-11-19 07:59:24,272 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-19 07:59:24,314 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-11-19 07:59:24,315 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-19 07:59:24,318 INFO L87 Difference]: Start difference. First operand has 118 states, 89 states have (on average 1.7415730337078652) internal successors, (155), 108 states have internal predecessors, (155), 23 states have call successors, (23), 4 states have call predecessors, (23), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) Second operand has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 07:59:24,368 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 07:59:24,368 INFO L93 Difference]: Finished difference Result 230 states and 397 transitions. [2023-11-19 07:59:24,369 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-11-19 07:59:24,371 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2023-11-19 07:59:24,371 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 07:59:24,381 INFO L225 Difference]: With dead ends: 230 [2023-11-19 07:59:24,381 INFO L226 Difference]: Without dead ends: 107 [2023-11-19 07:59:24,388 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-19 07:59:24,392 INFO L413 NwaCegarLoop]: 136 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, 136 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 [2023-11-19 07:59:24,394 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 136 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-19 07:59:24,415 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2023-11-19 07:59:24,446 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 107. [2023-11-19 07:59:24,448 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 82 states have (on average 1.2439024390243902) internal successors, (102), 97 states have internal predecessors, (102), 21 states have call successors, (21), 4 states have call predecessors, (21), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2023-11-19 07:59:24,453 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 128 transitions. [2023-11-19 07:59:24,454 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 128 transitions. Word has length 9 [2023-11-19 07:59:24,455 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 07:59:24,455 INFO L495 AbstractCegarLoop]: Abstraction has 107 states and 128 transitions. [2023-11-19 07:59:24,456 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 07:59:24,456 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 128 transitions. [2023-11-19 07:59:24,458 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2023-11-19 07:59:24,458 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 07:59:24,458 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 07:59:24,458 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-19 07:59:24,459 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 07:59:24,459 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 07:59:24,460 INFO L85 PathProgramCache]: Analyzing trace with hash 849043181, now seen corresponding path program 1 times [2023-11-19 07:59:24,460 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-19 07:59:24,460 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [426956136] [2023-11-19 07:59:24,460 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 07:59:24,461 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 07:59:24,537 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:24,890 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2023-11-19 07:59:24,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:24,967 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 07:59:24,968 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-19 07:59:24,968 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [426956136] [2023-11-19 07:59:24,968 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [426956136] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 07:59:24,969 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 07:59:24,969 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2023-11-19 07:59:24,969 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1813039730] [2023-11-19 07:59:24,969 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 07:59:24,971 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-19 07:59:24,971 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-19 07:59:24,973 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-19 07:59:24,973 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-19 07:59:24,973 INFO L87 Difference]: Start difference. First operand 107 states and 128 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 07:59:25,440 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 07:59:25,440 INFO L93 Difference]: Finished difference Result 109 states and 129 transitions. [2023-11-19 07:59:25,442 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-19 07:59:25,442 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 21 [2023-11-19 07:59:25,443 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 07:59:25,450 INFO L225 Difference]: With dead ends: 109 [2023-11-19 07:59:25,450 INFO L226 Difference]: Without dead ends: 106 [2023-11-19 07:59:25,451 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2023-11-19 07:59:25,453 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 242 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 211 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 245 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 245 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 211 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-19 07:59:25,453 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [245 Valid, 125 Invalid, 245 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 211 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-19 07:59:25,455 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2023-11-19 07:59:25,475 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 106. [2023-11-19 07:59:25,475 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 82 states have (on average 1.2317073170731707) internal successors, (101), 96 states have internal predecessors, (101), 20 states have call successors, (20), 4 states have call predecessors, (20), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2023-11-19 07:59:25,478 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 126 transitions. [2023-11-19 07:59:25,478 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 126 transitions. Word has length 21 [2023-11-19 07:59:25,479 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 07:59:25,479 INFO L495 AbstractCegarLoop]: Abstraction has 106 states and 126 transitions. [2023-11-19 07:59:25,480 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 07:59:25,480 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 126 transitions. [2023-11-19 07:59:25,481 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2023-11-19 07:59:25,481 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 07:59:25,481 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 07:59:25,481 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-19 07:59:25,482 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 07:59:25,482 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 07:59:25,482 INFO L85 PathProgramCache]: Analyzing trace with hash 502050183, now seen corresponding path program 1 times [2023-11-19 07:59:25,482 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-19 07:59:25,483 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [838314718] [2023-11-19 07:59:25,483 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 07:59:25,483 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 07:59:25,566 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:26,199 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2023-11-19 07:59:26,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:26,367 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 07:59:26,367 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-19 07:59:26,368 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [838314718] [2023-11-19 07:59:26,368 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [838314718] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 07:59:26,370 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 07:59:26,370 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2023-11-19 07:59:26,370 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1546201641] [2023-11-19 07:59:26,371 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 07:59:26,373 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-11-19 07:59:26,377 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-19 07:59:26,379 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-11-19 07:59:26,379 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=89, Unknown=0, NotChecked=0, Total=110 [2023-11-19 07:59:26,380 INFO L87 Difference]: Start difference. First operand 106 states and 126 transitions. Second operand has 11 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 07:59:27,522 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 07:59:27,523 INFO L93 Difference]: Finished difference Result 198 states and 235 transitions. [2023-11-19 07:59:27,525 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-19 07:59:27,526 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 24 [2023-11-19 07:59:27,527 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 07:59:27,537 INFO L225 Difference]: With dead ends: 198 [2023-11-19 07:59:27,538 INFO L226 Difference]: Without dead ends: 192 [2023-11-19 07:59:27,543 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 50 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=93, Invalid=327, Unknown=0, NotChecked=0, Total=420 [2023-11-19 07:59:27,545 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 481 mSDsluCounter, 142 mSDsCounter, 0 mSdLazyCounter, 767 mSolverCounterSat, 96 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 484 SdHoareTripleChecker+Valid, 171 SdHoareTripleChecker+Invalid, 863 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 96 IncrementalHoareTripleChecker+Valid, 767 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2023-11-19 07:59:27,548 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [484 Valid, 171 Invalid, 863 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [96 Valid, 767 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2023-11-19 07:59:27,551 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 192 states. [2023-11-19 07:59:27,615 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 192 to 172. [2023-11-19 07:59:27,616 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 172 states, 144 states have (on average 1.2430555555555556) internal successors, (179), 158 states have internal predecessors, (179), 23 states have call successors, (23), 6 states have call predecessors, (23), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-11-19 07:59:27,623 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 172 states to 172 states and 209 transitions. [2023-11-19 07:59:27,623 INFO L78 Accepts]: Start accepts. Automaton has 172 states and 209 transitions. Word has length 24 [2023-11-19 07:59:27,624 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 07:59:27,624 INFO L495 AbstractCegarLoop]: Abstraction has 172 states and 209 transitions. [2023-11-19 07:59:27,624 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 07:59:27,625 INFO L276 IsEmpty]: Start isEmpty. Operand 172 states and 209 transitions. [2023-11-19 07:59:27,626 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-11-19 07:59:27,626 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 07:59:27,626 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 07:59:27,626 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-11-19 07:59:27,627 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 07:59:27,627 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 07:59:27,628 INFO L85 PathProgramCache]: Analyzing trace with hash 1234303898, now seen corresponding path program 1 times [2023-11-19 07:59:27,628 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-19 07:59:27,628 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1029210759] [2023-11-19 07:59:27,628 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 07:59:27,629 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 07:59:27,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:28,617 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2023-11-19 07:59:28,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:28,952 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 07:59:28,952 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-19 07:59:28,953 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1029210759] [2023-11-19 07:59:28,953 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1029210759] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 07:59:28,953 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 07:59:28,953 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2023-11-19 07:59:28,954 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1617526829] [2023-11-19 07:59:28,954 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 07:59:28,955 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-11-19 07:59:28,955 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-19 07:59:28,956 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-11-19 07:59:28,956 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=90, Unknown=0, NotChecked=0, Total=110 [2023-11-19 07:59:28,956 INFO L87 Difference]: Start difference. First operand 172 states and 209 transitions. Second operand has 11 states, 11 states have (on average 2.090909090909091) internal successors, (23), 7 states have internal predecessors, (23), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 07:59:30,093 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 07:59:30,093 INFO L93 Difference]: Finished difference Result 274 states and 329 transitions. [2023-11-19 07:59:30,094 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-19 07:59:30,094 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.090909090909091) internal successors, (23), 7 states have internal predecessors, (23), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 27 [2023-11-19 07:59:30,095 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 07:59:30,097 INFO L225 Difference]: With dead ends: 274 [2023-11-19 07:59:30,098 INFO L226 Difference]: Without dead ends: 271 [2023-11-19 07:59:30,098 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=56, Invalid=216, Unknown=0, NotChecked=0, Total=272 [2023-11-19 07:59:30,108 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 307 mSDsluCounter, 207 mSDsCounter, 0 mSdLazyCounter, 951 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 310 SdHoareTripleChecker+Valid, 237 SdHoareTripleChecker+Invalid, 990 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 951 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2023-11-19 07:59:30,109 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [310 Valid, 237 Invalid, 990 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 951 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2023-11-19 07:59:30,111 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 271 states. [2023-11-19 07:59:30,164 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 271 to 253. [2023-11-19 07:59:30,165 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 253 states, 218 states have (on average 1.238532110091743) internal successors, (270), 233 states have internal predecessors, (270), 28 states have call successors, (28), 8 states have call predecessors, (28), 6 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-11-19 07:59:30,167 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 253 states to 253 states and 309 transitions. [2023-11-19 07:59:30,168 INFO L78 Accepts]: Start accepts. Automaton has 253 states and 309 transitions. Word has length 27 [2023-11-19 07:59:30,168 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 07:59:30,168 INFO L495 AbstractCegarLoop]: Abstraction has 253 states and 309 transitions. [2023-11-19 07:59:30,169 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.090909090909091) internal successors, (23), 7 states have internal predecessors, (23), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 07:59:30,169 INFO L276 IsEmpty]: Start isEmpty. Operand 253 states and 309 transitions. [2023-11-19 07:59:30,170 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2023-11-19 07:59:30,170 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 07:59:30,170 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 07:59:30,170 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-11-19 07:59:30,171 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 07:59:30,171 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 07:59:30,171 INFO L85 PathProgramCache]: Analyzing trace with hash 1680148119, now seen corresponding path program 1 times [2023-11-19 07:59:30,172 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-19 07:59:30,172 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [884154347] [2023-11-19 07:59:30,172 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 07:59:30,172 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 07:59:30,212 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:31,050 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2023-11-19 07:59:31,069 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:31,363 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 07:59:31,363 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-19 07:59:31,363 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [884154347] [2023-11-19 07:59:31,364 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [884154347] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 07:59:31,364 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 07:59:31,364 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2023-11-19 07:59:31,364 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [882236175] [2023-11-19 07:59:31,364 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 07:59:31,365 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-19 07:59:31,365 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-19 07:59:31,366 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-19 07:59:31,366 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=130, Unknown=0, NotChecked=0, Total=156 [2023-11-19 07:59:31,366 INFO L87 Difference]: Start difference. First operand 253 states and 309 transitions. Second operand has 13 states, 13 states have (on average 2.0) internal successors, (26), 9 states have internal predecessors, (26), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 07:59:32,846 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 07:59:32,847 INFO L93 Difference]: Finished difference Result 273 states and 327 transitions. [2023-11-19 07:59:32,847 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-11-19 07:59:32,847 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.0) internal successors, (26), 9 states have internal predecessors, (26), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 30 [2023-11-19 07:59:32,848 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 07:59:32,850 INFO L225 Difference]: With dead ends: 273 [2023-11-19 07:59:32,850 INFO L226 Difference]: Without dead ends: 270 [2023-11-19 07:59:32,851 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=82, Invalid=380, Unknown=0, NotChecked=0, Total=462 [2023-11-19 07:59:32,852 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 370 mSDsluCounter, 231 mSDsCounter, 0 mSdLazyCounter, 1054 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 370 SdHoareTripleChecker+Valid, 261 SdHoareTripleChecker+Invalid, 1103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 1054 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2023-11-19 07:59:32,853 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [370 Valid, 261 Invalid, 1103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 1054 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2023-11-19 07:59:32,854 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 270 states. [2023-11-19 07:59:32,924 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 270 to 253. [2023-11-19 07:59:32,925 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 253 states, 218 states have (on average 1.2339449541284404) internal successors, (269), 233 states have internal predecessors, (269), 28 states have call successors, (28), 8 states have call predecessors, (28), 6 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-11-19 07:59:32,927 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 253 states to 253 states and 308 transitions. [2023-11-19 07:59:32,928 INFO L78 Accepts]: Start accepts. Automaton has 253 states and 308 transitions. Word has length 30 [2023-11-19 07:59:32,928 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 07:59:32,928 INFO L495 AbstractCegarLoop]: Abstraction has 253 states and 308 transitions. [2023-11-19 07:59:32,928 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.0) internal successors, (26), 9 states have internal predecessors, (26), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 07:59:32,929 INFO L276 IsEmpty]: Start isEmpty. Operand 253 states and 308 transitions. [2023-11-19 07:59:32,930 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2023-11-19 07:59:32,931 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 07:59:32,931 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 07:59:32,931 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2023-11-19 07:59:32,932 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 07:59:32,932 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 07:59:32,932 INFO L85 PathProgramCache]: Analyzing trace with hash -493122043, now seen corresponding path program 1 times [2023-11-19 07:59:32,932 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-19 07:59:32,933 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [583320218] [2023-11-19 07:59:32,933 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 07:59:32,933 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 07:59:32,993 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:34,117 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2023-11-19 07:59:34,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:34,602 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 07:59:34,602 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-19 07:59:34,603 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [583320218] [2023-11-19 07:59:34,603 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [583320218] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 07:59:34,603 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 07:59:34,603 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2023-11-19 07:59:34,603 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1930857218] [2023-11-19 07:59:34,605 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 07:59:34,605 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-19 07:59:34,606 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-19 07:59:34,606 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-19 07:59:34,607 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=153, Unknown=0, NotChecked=0, Total=182 [2023-11-19 07:59:34,607 INFO L87 Difference]: Start difference. First operand 253 states and 308 transitions. Second operand has 14 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 07:59:36,254 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 07:59:36,254 INFO L93 Difference]: Finished difference Result 272 states and 325 transitions. [2023-11-19 07:59:36,255 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-11-19 07:59:36,255 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 33 [2023-11-19 07:59:36,255 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 07:59:36,257 INFO L225 Difference]: With dead ends: 272 [2023-11-19 07:59:36,258 INFO L226 Difference]: Without dead ends: 269 [2023-11-19 07:59:36,258 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=89, Invalid=373, Unknown=0, NotChecked=0, Total=462 [2023-11-19 07:59:36,259 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 346 mSDsluCounter, 255 mSDsCounter, 0 mSdLazyCounter, 1169 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 349 SdHoareTripleChecker+Valid, 285 SdHoareTripleChecker+Invalid, 1204 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 1169 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2023-11-19 07:59:36,260 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [349 Valid, 285 Invalid, 1204 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 1169 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2023-11-19 07:59:36,261 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 269 states. [2023-11-19 07:59:36,326 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 269 to 253. [2023-11-19 07:59:36,327 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 253 states, 218 states have (on average 1.2293577981651376) internal successors, (268), 233 states have internal predecessors, (268), 28 states have call successors, (28), 8 states have call predecessors, (28), 6 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-11-19 07:59:36,330 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 253 states to 253 states and 307 transitions. [2023-11-19 07:59:36,330 INFO L78 Accepts]: Start accepts. Automaton has 253 states and 307 transitions. Word has length 33 [2023-11-19 07:59:36,331 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 07:59:36,331 INFO L495 AbstractCegarLoop]: Abstraction has 253 states and 307 transitions. [2023-11-19 07:59:36,331 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 07:59:36,331 INFO L276 IsEmpty]: Start isEmpty. Operand 253 states and 307 transitions. [2023-11-19 07:59:36,338 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2023-11-19 07:59:36,339 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 07:59:36,339 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 07:59:36,339 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2023-11-19 07:59:36,339 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 07:59:36,340 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 07:59:36,340 INFO L85 PathProgramCache]: Analyzing trace with hash -2033122620, now seen corresponding path program 1 times [2023-11-19 07:59:36,340 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-19 07:59:36,341 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [679170525] [2023-11-19 07:59:36,341 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 07:59:36,341 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 07:59:36,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:37,527 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2023-11-19 07:59:37,541 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:37,879 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 07:59:37,879 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-19 07:59:37,879 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [679170525] [2023-11-19 07:59:37,880 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [679170525] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 07:59:37,880 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 07:59:37,880 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2023-11-19 07:59:37,880 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1652965534] [2023-11-19 07:59:37,880 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 07:59:37,901 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-11-19 07:59:37,901 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-19 07:59:37,902 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-11-19 07:59:37,902 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=110, Unknown=0, NotChecked=0, Total=132 [2023-11-19 07:59:37,902 INFO L87 Difference]: Start difference. First operand 253 states and 307 transitions. Second operand has 12 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 8 states have internal predecessors, (32), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 07:59:39,312 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 07:59:39,312 INFO L93 Difference]: Finished difference Result 271 states and 323 transitions. [2023-11-19 07:59:39,313 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-11-19 07:59:39,313 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 8 states have internal predecessors, (32), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 36 [2023-11-19 07:59:39,313 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 07:59:39,315 INFO L225 Difference]: With dead ends: 271 [2023-11-19 07:59:39,316 INFO L226 Difference]: Without dead ends: 268 [2023-11-19 07:59:39,316 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=66, Invalid=276, Unknown=0, NotChecked=0, Total=342 [2023-11-19 07:59:39,317 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 333 mSDsluCounter, 231 mSDsCounter, 0 mSdLazyCounter, 1056 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 336 SdHoareTripleChecker+Valid, 261 SdHoareTripleChecker+Invalid, 1089 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 1056 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2023-11-19 07:59:39,317 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [336 Valid, 261 Invalid, 1089 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 1056 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2023-11-19 07:59:39,318 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 268 states. [2023-11-19 07:59:39,369 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 268 to 253. [2023-11-19 07:59:39,370 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 253 states, 218 states have (on average 1.224770642201835) internal successors, (267), 233 states have internal predecessors, (267), 28 states have call successors, (28), 8 states have call predecessors, (28), 6 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-11-19 07:59:39,373 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 253 states to 253 states and 306 transitions. [2023-11-19 07:59:39,373 INFO L78 Accepts]: Start accepts. Automaton has 253 states and 306 transitions. Word has length 36 [2023-11-19 07:59:39,373 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 07:59:39,373 INFO L495 AbstractCegarLoop]: Abstraction has 253 states and 306 transitions. [2023-11-19 07:59:39,374 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 8 states have internal predecessors, (32), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 07:59:39,374 INFO L276 IsEmpty]: Start isEmpty. Operand 253 states and 306 transitions. [2023-11-19 07:59:39,375 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2023-11-19 07:59:39,375 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 07:59:39,375 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 07:59:39,375 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2023-11-19 07:59:39,376 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 07:59:39,376 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 07:59:39,376 INFO L85 PathProgramCache]: Analyzing trace with hash -1335339115, now seen corresponding path program 1 times [2023-11-19 07:59:39,376 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-19 07:59:39,377 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [907727363] [2023-11-19 07:59:39,377 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 07:59:39,377 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 07:59:39,411 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:40,162 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2023-11-19 07:59:40,174 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:40,341 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 07:59:40,342 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-19 07:59:40,342 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [907727363] [2023-11-19 07:59:40,342 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [907727363] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 07:59:40,342 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 07:59:40,343 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2023-11-19 07:59:40,343 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [648196802] [2023-11-19 07:59:40,343 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 07:59:40,343 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-11-19 07:59:40,344 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-19 07:59:40,344 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-11-19 07:59:40,345 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=110, Unknown=0, NotChecked=0, Total=132 [2023-11-19 07:59:40,345 INFO L87 Difference]: Start difference. First operand 253 states and 306 transitions. Second operand has 12 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 8 states have internal predecessors, (35), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 07:59:41,817 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 07:59:41,817 INFO L93 Difference]: Finished difference Result 270 states and 321 transitions. [2023-11-19 07:59:41,817 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2023-11-19 07:59:41,818 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 8 states have internal predecessors, (35), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 39 [2023-11-19 07:59:41,818 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 07:59:41,820 INFO L225 Difference]: With dead ends: 270 [2023-11-19 07:59:41,821 INFO L226 Difference]: Without dead ends: 267 [2023-11-19 07:59:41,821 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=104, Invalid=448, Unknown=0, NotChecked=0, Total=552 [2023-11-19 07:59:41,823 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 409 mSDsluCounter, 223 mSDsCounter, 0 mSdLazyCounter, 992 mSolverCounterSat, 47 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 412 SdHoareTripleChecker+Valid, 251 SdHoareTripleChecker+Invalid, 1039 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 47 IncrementalHoareTripleChecker+Valid, 992 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2023-11-19 07:59:41,824 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [412 Valid, 251 Invalid, 1039 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [47 Valid, 992 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2023-11-19 07:59:41,825 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 267 states. [2023-11-19 07:59:41,884 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 267 to 253. [2023-11-19 07:59:41,885 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 253 states, 218 states have (on average 1.2201834862385321) internal successors, (266), 233 states have internal predecessors, (266), 28 states have call successors, (28), 8 states have call predecessors, (28), 6 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-11-19 07:59:41,888 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 253 states to 253 states and 305 transitions. [2023-11-19 07:59:41,888 INFO L78 Accepts]: Start accepts. Automaton has 253 states and 305 transitions. Word has length 39 [2023-11-19 07:59:41,890 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 07:59:41,891 INFO L495 AbstractCegarLoop]: Abstraction has 253 states and 305 transitions. [2023-11-19 07:59:41,891 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 8 states have internal predecessors, (35), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-19 07:59:41,891 INFO L276 IsEmpty]: Start isEmpty. Operand 253 states and 305 transitions. [2023-11-19 07:59:41,893 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-11-19 07:59:41,893 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 07:59:41,894 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 07:59:41,894 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2023-11-19 07:59:41,894 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 07:59:41,895 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 07:59:41,895 INFO L85 PathProgramCache]: Analyzing trace with hash 1154705564, now seen corresponding path program 1 times [2023-11-19 07:59:41,895 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-19 07:59:41,895 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [33312580] [2023-11-19 07:59:41,896 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 07:59:41,896 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 07:59:41,963 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:43,565 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2023-11-19 07:59:43,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:43,828 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2023-11-19 07:59:43,839 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:44,053 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-19 07:59:44,054 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-19 07:59:44,054 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [33312580] [2023-11-19 07:59:44,054 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [33312580] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 07:59:44,055 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [309482734] [2023-11-19 07:59:44,055 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 07:59:44,055 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 07:59:44,055 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/z3 [2023-11-19 07:59:44,063 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 07:59:44,077 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-19 07:59:44,305 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 07:59:44,329 INFO L262 TraceCheckSpWp]: Trace formula consists of 364 conjuncts, 115 conjunts are in the unsatisfiable core [2023-11-19 07:59:44,338 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 07:59:44,473 INFO L349 Elim1Store]: treesize reduction 18, result has 35.7 percent of original size [2023-11-19 07:59:44,474 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 17 treesize of output 21 [2023-11-19 07:59:44,580 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 11 [2023-11-19 07:59:44,591 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 11 [2023-11-19 07:59:45,061 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 42 [2023-11-19 07:59:45,075 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 41 treesize of output 43 [2023-11-19 07:59:45,233 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-19 07:59:45,236 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 14 [2023-11-19 07:59:45,253 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 27 [2023-11-19 07:59:45,504 INFO L349 Elim1Store]: treesize reduction 24, result has 41.5 percent of original size [2023-11-19 07:59:45,504 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 2 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 25 treesize of output 29 [2023-11-19 07:59:45,596 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 25 [2023-11-19 07:59:45,815 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-19 07:59:45,846 INFO L349 Elim1Store]: treesize reduction 74, result has 12.9 percent of original size [2023-11-19 07:59:45,847 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 94 treesize of output 111 [2023-11-19 07:59:45,856 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-19 07:59:45,870 INFO L349 Elim1Store]: treesize reduction 17, result has 39.3 percent of original size [2023-11-19 07:59:45,870 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 81 treesize of output 69 [2023-11-19 07:59:45,887 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 67 treesize of output 25 [2023-11-19 07:59:45,960 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 18 [2023-11-19 07:59:46,175 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 8 [2023-11-19 07:59:46,219 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 07:59:46,219 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 07:59:46,660 WARN L854 $PredicateComparison]: unable to prove that (forall ((v_ArrVal_661 Int) (|v_list_add___list_add_~prev#1.offset_8| Int) (v_ArrVal_663 (Array Int Int)) (v_ArrVal_662 (Array Int Int)) (v_ArrVal_653 (Array Int Int))) (or (< |c_~#gl_list~0.offset| |v_list_add___list_add_~prev#1.offset_8|) (not (= (select (select (store (let ((.cse0 (store |c_#memory_$Pointer$.base| (select (select |c_#memory_$Pointer$.base| |c_~#gl_list~0.base|) |c_~#gl_list~0.offset|) v_ArrVal_663))) (store .cse0 |c_~#gl_list~0.base| (store (select (store .cse0 |c_ULTIMATE.start_gl_insert_~node~1#1.base| v_ArrVal_662) |c_~#gl_list~0.base|) |v_list_add___list_add_~prev#1.offset_8| v_ArrVal_661))) |c_ULTIMATE.start_gl_insert_~node~1#1.base| v_ArrVal_653) |c_~#gl_list~0.base|) (+ |c_~#gl_list~0.offset| 4)) |c_~#gl_list~0.base|)))) is different from false [2023-11-19 07:59:46,662 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [309482734] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 07:59:46,662 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 07:59:46,663 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 29 [2023-11-19 07:59:46,663 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1464118117] [2023-11-19 07:59:46,663 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 07:59:46,664 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2023-11-19 07:59:46,664 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-19 07:59:46,665 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2023-11-19 07:59:46,666 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=1079, Unknown=20, NotChecked=66, Total=1260 [2023-11-19 07:59:46,666 INFO L87 Difference]: Start difference. First operand 253 states and 305 transitions. Second operand has 30 states, 30 states have (on average 2.1666666666666665) internal successors, (65), 20 states have internal predecessors, (65), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-11-19 07:59:51,973 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-19 07:59:56,594 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-19 07:59:59,075 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-19 08:00:01,229 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-19 08:00:03,897 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-19 08:00:07,797 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-19 08:00:08,866 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 08:00:08,866 INFO L93 Difference]: Finished difference Result 468 states and 554 transitions. [2023-11-19 08:00:08,871 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2023-11-19 08:00:08,872 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 30 states have (on average 2.1666666666666665) internal successors, (65), 20 states have internal predecessors, (65), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 40 [2023-11-19 08:00:08,873 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 08:00:08,880 INFO L225 Difference]: With dead ends: 468 [2023-11-19 08:00:08,880 INFO L226 Difference]: Without dead ends: 465 [2023-11-19 08:00:08,884 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 42 SyntacticMatches, 0 SemanticMatches, 62 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 623 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=470, Invalid=3394, Unknown=46, NotChecked=122, Total=4032 [2023-11-19 08:00:08,887 INFO L413 NwaCegarLoop]: 50 mSDtfsCounter, 1755 mSDsluCounter, 821 mSDsCounter, 0 mSdLazyCounter, 4186 mSolverCounterSat, 336 mSolverCounterUnsat, 336 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 18.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1755 SdHoareTripleChecker+Valid, 871 SdHoareTripleChecker+Invalid, 4858 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.1s SdHoareTripleChecker+Time, 336 IncrementalHoareTripleChecker+Valid, 4186 IncrementalHoareTripleChecker+Invalid, 336 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 19.4s IncrementalHoareTripleChecker+Time [2023-11-19 08:00:08,887 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [1755 Valid, 871 Invalid, 4858 Unknown, 0 Unchecked, 0.1s Time], IncrementalHoareTripleChecker [336 Valid, 4186 Invalid, 336 Unknown, 0 Unchecked, 19.4s Time] [2023-11-19 08:00:08,889 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 465 states. [2023-11-19 08:00:08,964 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 465 to 351. [2023-11-19 08:00:08,965 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 351 states, 306 states have (on average 1.2156862745098038) internal successors, (372), 322 states have internal predecessors, (372), 34 states have call successors, (34), 12 states have call predecessors, (34), 10 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2023-11-19 08:00:08,968 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 351 states to 351 states and 422 transitions. [2023-11-19 08:00:08,969 INFO L78 Accepts]: Start accepts. Automaton has 351 states and 422 transitions. Word has length 40 [2023-11-19 08:00:08,969 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 08:00:08,969 INFO L495 AbstractCegarLoop]: Abstraction has 351 states and 422 transitions. [2023-11-19 08:00:08,970 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 30 states have (on average 2.1666666666666665) internal successors, (65), 20 states have internal predecessors, (65), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-11-19 08:00:08,970 INFO L276 IsEmpty]: Start isEmpty. Operand 351 states and 422 transitions. [2023-11-19 08:00:08,971 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2023-11-19 08:00:08,971 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 08:00:08,971 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 08:00:08,994 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-11-19 08:00:09,191 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_29effa46-264a-43dc-a648-7761e8da4e13/bin/uautomizer-verify-uCwYo4JHxu/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2023-11-19 08:00:09,192 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 08:00:09,192 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 08:00:09,193 INFO L85 PathProgramCache]: Analyzing trace with hash -1293265745, now seen corresponding path program 1 times [2023-11-19 08:00:09,193 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-19 08:00:09,193 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [7511828] [2023-11-19 08:00:09,193 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 08:00:09,198 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 08:00:09,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat