./Ultimate.py --spec ../../../trunk/examples/svcomp/properties/unreach-call.prp --file ../../../trunk/examples/svcomp/aws-c-common/aws_array_list_clean_up_harness_negated.i --full-output --preprocessor.use.memory.slicer true --architecture 64bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version abd6749d Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../../../trunk/examples/svcomp/aws-c-common/aws_array_list_clean_up_harness_negated.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 64bit --witnessprinter.graph.data.programhash 78cfcf98f3ab19f40588d2571f280986dd2c4e42f9e3bdc2b5b4043a7bab148a --preprocessor.use.memory.slicer true --- Real Ultimate output --- This is Ultimate 0.2.3-?-abd6749-m [2023-11-23 06:34:37,502 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-23 06:34:37,538 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf [2023-11-23 06:34:37,541 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-23 06:34:37,541 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-23 06:34:37,570 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-23 06:34:37,571 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-23 06:34:37,571 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-23 06:34:37,571 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-11-23 06:34:37,572 INFO L153 SettingsManager]: * Use memory slicer=true [2023-11-23 06:34:37,572 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-23 06:34:37,572 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-23 06:34:37,573 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-11-23 06:34:37,573 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-11-23 06:34:37,573 INFO L153 SettingsManager]: * Use SBE=true [2023-11-23 06:34:37,574 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-23 06:34:37,574 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-23 06:34:37,574 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-23 06:34:37,575 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-23 06:34:37,575 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-23 06:34:37,575 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-23 06:34:37,576 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-23 06:34:37,576 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-23 06:34:37,576 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-23 06:34:37,577 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-23 06:34:37,577 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-11-23 06:34:37,577 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-11-23 06:34:37,577 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-23 06:34:37,578 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-23 06:34:37,578 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-23 06:34:37,578 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-23 06:34:37,579 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-23 06:34:37,579 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-11-23 06:34:37,579 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-23 06:34:37,580 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-11-23 06:34:37,580 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-11-23 06:34:37,580 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-23 06:34:37,581 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-11-23 06:34:37,581 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-23 06:34:37,581 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:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/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 -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 78cfcf98f3ab19f40588d2571f280986dd2c4e42f9e3bdc2b5b4043a7bab148a Applying setting for plugin de.uni_freiburg.informatik.ultimate.boogie.preprocessor: Use memory slicer -> true [2023-11-23 06:34:37,800 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-23 06:34:37,823 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-23 06:34:37,825 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-23 06:34:37,826 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-23 06:34:37,826 INFO L274 PluginConnector]: CDTParser initialized [2023-11-23 06:34:37,827 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/aws-c-common/aws_array_list_clean_up_harness_negated.i [2023-11-23 06:34:38,953 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-23 06:34:39,311 INFO L384 CDTParser]: Found 1 translation units. [2023-11-23 06:34:39,311 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_array_list_clean_up_harness_negated.i [2023-11-23 06:34:39,339 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5bfc171df/19ced9ba180f46f9989817cfa9029fab/FLAGc0dd67312 [2023-11-23 06:34:39,354 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5bfc171df/19ced9ba180f46f9989817cfa9029fab [2023-11-23 06:34:39,357 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-23 06:34:39,360 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-23 06:34:39,362 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-23 06:34:39,363 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-23 06:34:39,366 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-23 06:34:39,367 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 06:34:39" (1/1) ... [2023-11-23 06:34:39,367 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7e6ce2e6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 06:34:39, skipping insertion in model container [2023-11-23 06:34:39,368 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 06:34:39" (1/1) ... [2023-11-23 06:34:39,449 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-23 06:34:39,631 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_array_list_clean_up_harness_negated.i[4497,4510] [2023-11-23 06:34:39,639 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_array_list_clean_up_harness_negated.i[4557,4570] [2023-11-23 06:34:40,249 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,252 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,252 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,256 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,257 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,268 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,272 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,273 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,274 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,276 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,287 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,289 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,290 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,512 WARN L635 FunctionHandler]: implicit declaration of function __atomic_load_n [2023-11-23 06:34:40,513 WARN L635 FunctionHandler]: implicit declaration of function __atomic_store_n [2023-11-23 06:34:40,514 WARN L635 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2023-11-23 06:34:40,515 WARN L635 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2023-11-23 06:34:40,516 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2023-11-23 06:34:40,516 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2023-11-23 06:34:40,517 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2023-11-23 06:34:40,517 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2023-11-23 06:34:40,517 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2023-11-23 06:34:40,518 WARN L635 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2023-11-23 06:34:40,596 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,617 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,661 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-23 06:34:40,696 INFO L202 MainTranslator]: Completed pre-run [2023-11-23 06:34:40,750 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_array_list_clean_up_harness_negated.i[4497,4510] [2023-11-23 06:34:40,751 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_array_list_clean_up_harness_negated.i[4557,4570] [2023-11-23 06:34:40,848 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,852 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,853 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,853 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,858 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,863 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,865 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,866 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,866 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,869 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,869 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,870 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,870 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,903 WARN L635 FunctionHandler]: implicit declaration of function __atomic_load_n [2023-11-23 06:34:40,904 WARN L635 FunctionHandler]: implicit declaration of function __atomic_store_n [2023-11-23 06:34:40,904 WARN L635 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2023-11-23 06:34:40,905 WARN L635 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2023-11-23 06:34:40,907 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2023-11-23 06:34:40,908 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2023-11-23 06:34:40,908 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2023-11-23 06:34:40,909 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2023-11-23 06:34:40,909 WARN L635 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2023-11-23 06:34:40,909 WARN L635 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2023-11-23 06:34:40,925 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,932 WARN L1590 CHandler]: Possible shadowing of function index [2023-11-23 06:34:40,941 WARN L75 lationResultReporter]: Unsoundness Warning: Ignoring inline assembler instruction C: __asm__ __volatile__("" : : "r"(pBuf) : "memory"); [7517-7528] [2023-11-23 06:34:40,959 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-23 06:34:41,110 WARN L675 CHandler]: The function __atomic_fetch_or is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 06:34:41,111 WARN L675 CHandler]: The function __atomic_fetch_sub is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 06:34:41,111 WARN L675 CHandler]: The function __atomic_exchange_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 06:34:41,111 WARN L675 CHandler]: The function __atomic_fetch_xor is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 06:34:41,111 WARN L675 CHandler]: The function htons is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 06:34:41,111 WARN L675 CHandler]: The function ntohl is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 06:34:41,112 WARN L675 CHandler]: The function __atomic_compare_exchange_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 06:34:41,112 WARN L675 CHandler]: The function __atomic_fetch_add is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 06:34:41,112 WARN L675 CHandler]: The function fprintf is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 06:34:41,112 WARN L675 CHandler]: The function htonl is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 06:34:41,112 WARN L675 CHandler]: The function __atomic_store_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 06:34:41,113 WARN L675 CHandler]: The function ntohs is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 06:34:41,113 WARN L675 CHandler]: The function __atomic_load_n is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 06:34:41,113 WARN L675 CHandler]: The function __atomic_thread_fence is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 06:34:41,113 WARN L675 CHandler]: The function __atomic_fetch_and is called, but not defined or handled by StandardFunctionHandler. [2023-11-23 06:34:41,119 INFO L206 MainTranslator]: Completed translation [2023-11-23 06:34:41,120 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 06:34:41 WrapperNode [2023-11-23 06:34:41,120 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-23 06:34:41,121 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-23 06:34:41,121 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-23 06:34:41,121 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-23 06:34:41,126 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 06:34:41" (1/1) ... [2023-11-23 06:34:41,197 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 06:34:41" (1/1) ... [2023-11-23 06:34:41,241 INFO L138 Inliner]: procedures = 689, calls = 1554, calls flagged for inlining = 48, calls inlined = 7, statements flattened = 578 [2023-11-23 06:34:41,241 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-23 06:34:41,242 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-23 06:34:41,242 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-23 06:34:41,242 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-23 06:34:41,250 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 06:34:41" (1/1) ... [2023-11-23 06:34:41,251 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 06:34:41" (1/1) ... [2023-11-23 06:34:41,256 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 06:34:41" (1/1) ... [2023-11-23 06:34:41,332 INFO L188 MemorySlicer]: Split 278 memory accesses to 7 slices as follows [2, 236, 0, 3, 28, 6, 3]. 85 percent of accesses are in the largest equivalence class. The 252 initializations are split as follows [2, 236, 0, 1, 5, 5, 3]. The 5 writes are split as follows [0, 0, 0, 1, 4, 0, 0]. [2023-11-23 06:34:41,332 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 06:34:41" (1/1) ... [2023-11-23 06:34:41,333 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 06:34:41" (1/1) ... [2023-11-23 06:34:41,366 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 06:34:41" (1/1) ... [2023-11-23 06:34:41,374 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 06:34:41" (1/1) ... [2023-11-23 06:34:41,389 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 06:34:41" (1/1) ... [2023-11-23 06:34:41,399 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 06:34:41" (1/1) ... [2023-11-23 06:34:41,405 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-23 06:34:41,409 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-23 06:34:41,409 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-23 06:34:41,409 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-23 06:34:41,410 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 06:34:41" (1/1) ... [2023-11-23 06:34:41,416 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-23 06:34:41,425 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 06:34:41,437 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-23 06:34:41,443 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-23 06:34:41,481 INFO L130 BoogieDeclarations]: Found specification of procedure aws_is_mem_zeroed [2023-11-23 06:34:41,481 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_is_mem_zeroed [2023-11-23 06:34:41,481 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-11-23 06:34:41,481 INFO L130 BoogieDeclarations]: Found specification of procedure aws_array_list_is_bounded [2023-11-23 06:34:41,481 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_array_list_is_bounded [2023-11-23 06:34:41,481 INFO L130 BoogieDeclarations]: Found specification of procedure aws_array_list_is_valid [2023-11-23 06:34:41,482 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_array_list_is_valid [2023-11-23 06:34:41,482 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_bool [2023-11-23 06:34:41,482 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_bool [2023-11-23 06:34:41,482 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2023-11-23 06:34:41,483 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2023-11-23 06:34:41,483 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2023-11-23 06:34:41,483 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2023-11-23 06:34:41,483 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2023-11-23 06:34:41,483 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2023-11-23 06:34:41,483 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#6 [2023-11-23 06:34:41,483 INFO L130 BoogieDeclarations]: Found specification of procedure aws_raise_error [2023-11-23 06:34:41,483 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_raise_error [2023-11-23 06:34:41,483 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-23 06:34:41,484 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-23 06:34:41,484 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2023-11-23 06:34:41,484 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-23 06:34:41,484 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2023-11-23 06:34:41,484 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2023-11-23 06:34:41,485 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2023-11-23 06:34:41,485 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#3 [2023-11-23 06:34:41,485 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#4 [2023-11-23 06:34:41,485 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#5 [2023-11-23 06:34:41,485 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#6 [2023-11-23 06:34:41,485 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-23 06:34:41,485 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-23 06:34:41,485 INFO L130 BoogieDeclarations]: Found specification of procedure bounded_malloc [2023-11-23 06:34:41,486 INFO L138 BoogieDeclarations]: Found implementation of procedure bounded_malloc [2023-11-23 06:34:41,486 INFO L130 BoogieDeclarations]: Found specification of procedure aws_mul_size_checked [2023-11-23 06:34:41,486 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_mul_size_checked [2023-11-23 06:34:41,486 INFO L130 BoogieDeclarations]: Found specification of procedure aws_mem_release [2023-11-23 06:34:41,486 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_mem_release [2023-11-23 06:34:41,487 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.C_memset#0 [2023-11-23 06:34:41,487 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.C_memset#1 [2023-11-23 06:34:41,487 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.C_memset#2 [2023-11-23 06:34:41,487 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.C_memset#3 [2023-11-23 06:34:41,487 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.C_memset#4 [2023-11-23 06:34:41,487 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.C_memset#5 [2023-11-23 06:34:41,487 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.C_memset#6 [2023-11-23 06:34:41,487 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.C_memset#0 [2023-11-23 06:34:41,488 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.C_memset#1 [2023-11-23 06:34:41,488 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.C_memset#2 [2023-11-23 06:34:41,488 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.C_memset#3 [2023-11-23 06:34:41,488 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.C_memset#4 [2023-11-23 06:34:41,488 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.C_memset#5 [2023-11-23 06:34:41,488 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.C_memset#6 [2023-11-23 06:34:41,488 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-11-23 06:34:41,488 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-11-23 06:34:41,489 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-11-23 06:34:41,489 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2023-11-23 06:34:41,489 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2023-11-23 06:34:41,489 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2023-11-23 06:34:41,489 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#3 [2023-11-23 06:34:41,489 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#4 [2023-11-23 06:34:41,489 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#5 [2023-11-23 06:34:41,489 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#6 [2023-11-23 06:34:41,489 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2023-11-23 06:34:41,490 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2023-11-23 06:34:41,490 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2023-11-23 06:34:41,491 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#3 [2023-11-23 06:34:41,491 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#4 [2023-11-23 06:34:41,491 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#5 [2023-11-23 06:34:41,491 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#6 [2023-11-23 06:34:41,491 INFO L130 BoogieDeclarations]: Found specification of procedure can_fail_allocator [2023-11-23 06:34:41,491 INFO L138 BoogieDeclarations]: Found implementation of procedure can_fail_allocator [2023-11-23 06:34:41,491 INFO L130 BoogieDeclarations]: Found specification of procedure __CPROVER_overflow_mult [2023-11-23 06:34:41,492 INFO L138 BoogieDeclarations]: Found implementation of procedure __CPROVER_overflow_mult [2023-11-23 06:34:41,492 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2023-11-23 06:34:41,492 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2023-11-23 06:34:41,492 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2023-11-23 06:34:41,492 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2023-11-23 06:34:41,493 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2023-11-23 06:34:41,493 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2023-11-23 06:34:41,493 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#6 [2023-11-23 06:34:41,493 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-11-23 06:34:41,494 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2023-11-23 06:34:41,494 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2023-11-23 06:34:41,496 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2023-11-23 06:34:41,496 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2023-11-23 06:34:41,496 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2023-11-23 06:34:41,496 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#6 [2023-11-23 06:34:41,746 INFO L241 CfgBuilder]: Building ICFG [2023-11-23 06:34:41,755 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-23 06:34:42,379 INFO L282 CfgBuilder]: Performing block encoding [2023-11-23 06:34:42,454 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-23 06:34:42,455 INFO L309 CfgBuilder]: Removed 3 assume(true) statements. [2023-11-23 06:34:42,455 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 06:34:42 BoogieIcfgContainer [2023-11-23 06:34:42,460 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-23 06:34:42,462 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-23 06:34:42,462 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-23 06:34:42,464 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-23 06:34:42,464 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.11 06:34:39" (1/3) ... [2023-11-23 06:34:42,465 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6a9b34e9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 06:34:42, skipping insertion in model container [2023-11-23 06:34:42,465 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 06:34:41" (2/3) ... [2023-11-23 06:34:42,466 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6a9b34e9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 06:34:42, skipping insertion in model container [2023-11-23 06:34:42,466 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 06:34:42" (3/3) ... [2023-11-23 06:34:42,468 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_array_list_clean_up_harness_negated.i [2023-11-23 06:34:42,480 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-23 06:34:42,481 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-23 06:34:42,519 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-23 06:34:42,524 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;@4f300714, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-23 06:34:42,524 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-23 06:34:42,527 INFO L276 IsEmpty]: Start isEmpty. Operand has 100 states, 64 states have (on average 1.3125) internal successors, (84), 64 states have internal predecessors, (84), 22 states have call successors, (22), 13 states have call predecessors, (22), 13 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2023-11-23 06:34:42,534 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2023-11-23 06:34:42,535 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:34:42,535 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 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-23 06:34:42,535 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:34:42,539 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:34:42,539 INFO L85 PathProgramCache]: Analyzing trace with hash 1074526324, now seen corresponding path program 1 times [2023-11-23 06:34:42,545 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:34:42,546 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2026965567] [2023-11-23 06:34:42,546 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:42,546 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:34:42,791 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:42,991 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 06:34:42,993 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:43,003 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-23 06:34:43,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:43,010 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2023-11-23 06:34:43,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:43,015 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2023-11-23 06:34:43,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:43,125 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2023-11-23 06:34:43,129 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:43,136 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2023-11-23 06:34:43,137 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:43,141 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2023-11-23 06:34:43,142 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:43,146 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2023-11-23 06:34:43,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:43,151 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2023-11-23 06:34:43,152 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:43,156 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2023-11-23 06:34:43,157 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 06:34:43,157 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2026965567] [2023-11-23 06:34:43,157 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2026965567] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 06:34:43,158 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 06:34:43,158 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-23 06:34:43,159 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [964736325] [2023-11-23 06:34:43,159 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 06:34:43,162 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-23 06:34:43,163 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 06:34:43,180 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-23 06:34:43,181 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-23 06:34:43,183 INFO L87 Difference]: Start difference. First operand has 100 states, 64 states have (on average 1.3125) internal successors, (84), 64 states have internal predecessors, (84), 22 states have call successors, (22), 13 states have call predecessors, (22), 13 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) Second operand has 3 states, 3 states have (on average 10.0) internal successors, (30), 2 states have internal predecessors, (30), 2 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2023-11-23 06:34:43,543 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 06:34:43,544 INFO L93 Difference]: Finished difference Result 201 states and 270 transitions. [2023-11-23 06:34:43,545 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-23 06:34:43,546 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 10.0) internal successors, (30), 2 states have internal predecessors, (30), 2 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 62 [2023-11-23 06:34:43,546 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 06:34:43,552 INFO L225 Difference]: With dead ends: 201 [2023-11-23 06:34:43,552 INFO L226 Difference]: Without dead ends: 102 [2023-11-23 06:34:43,555 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-23 06:34:43,557 INFO L413 NwaCegarLoop]: 84 mSDtfsCounter, 30 mSDsluCounter, 29 mSDsCounter, 0 mSdLazyCounter, 84 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 106 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 84 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-23 06:34:43,558 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 113 Invalid, 106 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 84 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-23 06:34:43,569 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2023-11-23 06:34:43,588 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 96. [2023-11-23 06:34:43,589 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 61 states have (on average 1.2459016393442623) internal successors, (76), 61 states have internal predecessors, (76), 22 states have call successors, (22), 13 states have call predecessors, (22), 12 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) [2023-11-23 06:34:43,590 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 119 transitions. [2023-11-23 06:34:43,591 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 119 transitions. Word has length 62 [2023-11-23 06:34:43,592 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 06:34:43,592 INFO L495 AbstractCegarLoop]: Abstraction has 96 states and 119 transitions. [2023-11-23 06:34:43,592 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 10.0) internal successors, (30), 2 states have internal predecessors, (30), 2 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2023-11-23 06:34:43,592 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 119 transitions. [2023-11-23 06:34:43,594 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2023-11-23 06:34:43,594 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:34:43,594 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1] [2023-11-23 06:34:43,595 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-23 06:34:43,595 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:34:43,595 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:34:43,595 INFO L85 PathProgramCache]: Analyzing trace with hash -1079087629, now seen corresponding path program 1 times [2023-11-23 06:34:43,596 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:34:43,596 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [226660324] [2023-11-23 06:34:43,596 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:43,596 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:34:43,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:43,879 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 06:34:43,883 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:43,895 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-23 06:34:43,901 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:43,907 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2023-11-23 06:34:43,912 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:43,924 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2023-11-23 06:34:43,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:44,034 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2023-11-23 06:34:44,038 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:44,101 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2023-11-23 06:34:44,104 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:44,109 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2023-11-23 06:34:44,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:44,118 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2023-11-23 06:34:44,119 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:44,137 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 50 [2023-11-23 06:34:44,140 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:44,145 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 57 [2023-11-23 06:34:44,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:44,155 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2023-11-23 06:34:44,155 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 06:34:44,156 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [226660324] [2023-11-23 06:34:44,156 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [226660324] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 06:34:44,156 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 06:34:44,156 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2023-11-23 06:34:44,156 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [46619760] [2023-11-23 06:34:44,157 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 06:34:44,161 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-11-23 06:34:44,161 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 06:34:44,162 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-11-23 06:34:44,162 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-23 06:34:44,162 INFO L87 Difference]: Start difference. First operand 96 states and 119 transitions. Second operand has 7 states, 7 states have (on average 4.714285714285714) internal successors, (33), 5 states have internal predecessors, (33), 2 states have call successors, (11), 4 states have call predecessors, (11), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2023-11-23 06:34:44,911 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 06:34:44,911 INFO L93 Difference]: Finished difference Result 169 states and 209 transitions. [2023-11-23 06:34:44,912 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-11-23 06:34:44,912 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 4.714285714285714) internal successors, (33), 5 states have internal predecessors, (33), 2 states have call successors, (11), 4 states have call predecessors, (11), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 67 [2023-11-23 06:34:44,912 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 06:34:44,916 INFO L225 Difference]: With dead ends: 169 [2023-11-23 06:34:44,916 INFO L226 Difference]: Without dead ends: 102 [2023-11-23 06:34:44,918 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2023-11-23 06:34:44,919 INFO L413 NwaCegarLoop]: 69 mSDtfsCounter, 84 mSDsluCounter, 168 mSDsCounter, 0 mSdLazyCounter, 303 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 101 SdHoareTripleChecker+Valid, 237 SdHoareTripleChecker+Invalid, 327 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 303 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-23 06:34:44,921 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [101 Valid, 237 Invalid, 327 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 303 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-23 06:34:44,923 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2023-11-23 06:34:44,940 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 98. [2023-11-23 06:34:44,941 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 62 states have (on average 1.2419354838709677) internal successors, (77), 63 states have internal predecessors, (77), 22 states have call successors, (22), 13 states have call predecessors, (22), 13 states have return successors, (22), 21 states have call predecessors, (22), 21 states have call successors, (22) [2023-11-23 06:34:44,944 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 121 transitions. [2023-11-23 06:34:44,944 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 121 transitions. Word has length 67 [2023-11-23 06:34:44,944 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 06:34:44,945 INFO L495 AbstractCegarLoop]: Abstraction has 98 states and 121 transitions. [2023-11-23 06:34:44,945 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 4.714285714285714) internal successors, (33), 5 states have internal predecessors, (33), 2 states have call successors, (11), 4 states have call predecessors, (11), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2023-11-23 06:34:44,945 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 121 transitions. [2023-11-23 06:34:44,949 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2023-11-23 06:34:44,949 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:34:44,950 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 06:34:44,950 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-23 06:34:44,950 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:34:44,950 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:34:44,951 INFO L85 PathProgramCache]: Analyzing trace with hash 44503419, now seen corresponding path program 1 times [2023-11-23 06:34:44,951 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:34:44,951 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2095297969] [2023-11-23 06:34:44,951 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:44,951 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:34:45,023 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 06:34:45,023 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1102791571] [2023-11-23 06:34:45,023 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:45,024 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:45,024 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 06:34:45,025 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 06:34:45,053 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-23 06:34:45,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:45,425 INFO L262 TraceCheckSpWp]: Trace formula consists of 2207 conjuncts, 9 conjunts are in the unsatisfiable core [2023-11-23 06:34:45,432 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 06:34:45,471 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 17 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-23 06:34:45,471 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-23 06:34:45,471 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 06:34:45,472 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2095297969] [2023-11-23 06:34:45,472 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 06:34:45,472 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1102791571] [2023-11-23 06:34:45,472 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1102791571] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 06:34:45,472 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 06:34:45,472 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-23 06:34:45,473 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1559016049] [2023-11-23 06:34:45,473 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 06:34:45,473 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-23 06:34:45,473 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 06:34:45,474 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-23 06:34:45,474 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-23 06:34:45,474 INFO L87 Difference]: Start difference. First operand 98 states and 121 transitions. Second operand has 4 states, 4 states have (on average 12.25) internal successors, (49), 4 states have internal predecessors, (49), 2 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2023-11-23 06:34:45,726 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 06:34:45,726 INFO L93 Difference]: Finished difference Result 171 states and 211 transitions. [2023-11-23 06:34:45,727 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-23 06:34:45,727 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 12.25) internal successors, (49), 4 states have internal predecessors, (49), 2 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 80 [2023-11-23 06:34:45,727 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 06:34:45,728 INFO L225 Difference]: With dead ends: 171 [2023-11-23 06:34:45,728 INFO L226 Difference]: Without dead ends: 102 [2023-11-23 06:34:45,729 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 77 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2023-11-23 06:34:45,729 INFO L413 NwaCegarLoop]: 105 mSDtfsCounter, 6 mSDsluCounter, 205 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 310 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-23 06:34:45,730 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 310 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-23 06:34:45,730 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2023-11-23 06:34:45,739 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 99. [2023-11-23 06:34:45,739 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 63 states have (on average 1.2380952380952381) internal successors, (78), 64 states have internal predecessors, (78), 22 states have call successors, (22), 13 states have call predecessors, (22), 13 states have return successors, (22), 21 states have call predecessors, (22), 21 states have call successors, (22) [2023-11-23 06:34:45,740 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 122 transitions. [2023-11-23 06:34:45,740 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 122 transitions. Word has length 80 [2023-11-23 06:34:45,740 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 06:34:45,741 INFO L495 AbstractCegarLoop]: Abstraction has 99 states and 122 transitions. [2023-11-23 06:34:45,741 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 12.25) internal successors, (49), 4 states have internal predecessors, (49), 2 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2023-11-23 06:34:45,741 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 122 transitions. [2023-11-23 06:34:45,742 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2023-11-23 06:34:45,742 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:34:45,742 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 06:34:45,761 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-23 06:34:45,955 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:45,955 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:34:45,956 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:34:45,956 INFO L85 PathProgramCache]: Analyzing trace with hash -2060014693, now seen corresponding path program 1 times [2023-11-23 06:34:45,957 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:34:45,957 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1615458675] [2023-11-23 06:34:45,957 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:45,957 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:34:46,009 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 06:34:46,010 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [88374181] [2023-11-23 06:34:46,010 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:46,010 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:46,010 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 06:34:46,011 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 06:34:46,036 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-23 06:34:46,387 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:46,395 INFO L262 TraceCheckSpWp]: Trace formula consists of 2213 conjuncts, 12 conjunts are in the unsatisfiable core [2023-11-23 06:34:46,399 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 06:34:46,433 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-11-23 06:34:46,434 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-23 06:34:46,434 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 06:34:46,434 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1615458675] [2023-11-23 06:34:46,434 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 06:34:46,434 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [88374181] [2023-11-23 06:34:46,434 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [88374181] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 06:34:46,435 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 06:34:46,435 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2023-11-23 06:34:46,435 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2072509973] [2023-11-23 06:34:46,435 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 06:34:46,435 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-23 06:34:46,436 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 06:34:46,436 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-23 06:34:46,436 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-23 06:34:46,436 INFO L87 Difference]: Start difference. First operand 99 states and 122 transitions. Second operand has 6 states, 5 states have (on average 9.2) internal successors, (46), 6 states have internal predecessors, (46), 2 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2023-11-23 06:34:46,768 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 06:34:46,768 INFO L93 Difference]: Finished difference Result 120 states and 147 transitions. [2023-11-23 06:34:46,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-23 06:34:46,769 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 9.2) internal successors, (46), 6 states have internal predecessors, (46), 2 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 80 [2023-11-23 06:34:46,769 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 06:34:46,770 INFO L225 Difference]: With dead ends: 120 [2023-11-23 06:34:46,770 INFO L226 Difference]: Without dead ends: 103 [2023-11-23 06:34:46,770 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2023-11-23 06:34:46,771 INFO L413 NwaCegarLoop]: 104 mSDtfsCounter, 10 mSDsluCounter, 405 mSDsCounter, 0 mSdLazyCounter, 75 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 509 SdHoareTripleChecker+Invalid, 77 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 75 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-23 06:34:46,771 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 509 Invalid, 77 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 75 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-23 06:34:46,772 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2023-11-23 06:34:46,779 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 100. [2023-11-23 06:34:46,780 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 64 states have (on average 1.234375) internal successors, (79), 65 states have internal predecessors, (79), 22 states have call successors, (22), 13 states have call predecessors, (22), 13 states have return successors, (22), 21 states have call predecessors, (22), 21 states have call successors, (22) [2023-11-23 06:34:46,780 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 123 transitions. [2023-11-23 06:34:46,780 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 123 transitions. Word has length 80 [2023-11-23 06:34:46,781 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 06:34:46,781 INFO L495 AbstractCegarLoop]: Abstraction has 100 states and 123 transitions. [2023-11-23 06:34:46,781 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 9.2) internal successors, (46), 6 states have internal predecessors, (46), 2 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2023-11-23 06:34:46,781 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 123 transitions. [2023-11-23 06:34:46,782 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2023-11-23 06:34:46,782 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:34:46,782 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 06:34:46,812 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-23 06:34:46,996 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2023-11-23 06:34:46,996 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:34:46,997 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:34:46,997 INFO L85 PathProgramCache]: Analyzing trace with hash -387568358, now seen corresponding path program 1 times [2023-11-23 06:34:46,997 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:34:46,997 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [295857348] [2023-11-23 06:34:46,997 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:46,998 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:34:47,072 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 06:34:47,073 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1828301628] [2023-11-23 06:34:47,073 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:47,073 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:47,073 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 06:34:47,089 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 06:34:47,095 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-23 06:34:47,471 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:47,479 INFO L262 TraceCheckSpWp]: Trace formula consists of 2232 conjuncts, 44 conjunts are in the unsatisfiable core [2023-11-23 06:34:47,484 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 06:34:47,554 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-23 06:34:47,663 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 1 proven. 5 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-11-23 06:34:47,663 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 06:34:47,853 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 27 treesize of output 23 [2023-11-23 06:34:47,902 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 14 treesize of output 12 [2023-11-23 06:34:47,904 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 14 [2023-11-23 06:34:47,977 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2023-11-23 06:34:47,978 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 06:34:47,978 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [295857348] [2023-11-23 06:34:47,978 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 06:34:47,978 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1828301628] [2023-11-23 06:34:47,978 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1828301628] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 06:34:47,978 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 06:34:47,978 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 18 [2023-11-23 06:34:47,978 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1900397369] [2023-11-23 06:34:47,978 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 06:34:47,978 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-11-23 06:34:47,979 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 06:34:47,979 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-11-23 06:34:47,979 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=259, Unknown=0, NotChecked=0, Total=306 [2023-11-23 06:34:47,979 INFO L87 Difference]: Start difference. First operand 100 states and 123 transitions. Second operand has 18 states, 18 states have (on average 3.388888888888889) internal successors, (61), 17 states have internal predecessors, (61), 5 states have call successors, (14), 3 states have call predecessors, (14), 6 states have return successors, (15), 5 states have call predecessors, (15), 4 states have call successors, (15) [2023-11-23 06:34:49,718 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 06:34:49,718 INFO L93 Difference]: Finished difference Result 118 states and 143 transitions. [2023-11-23 06:34:49,720 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-11-23 06:34:49,720 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 3.388888888888889) internal successors, (61), 17 states have internal predecessors, (61), 5 states have call successors, (14), 3 states have call predecessors, (14), 6 states have return successors, (15), 5 states have call predecessors, (15), 4 states have call successors, (15) Word has length 81 [2023-11-23 06:34:49,720 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 06:34:49,721 INFO L225 Difference]: With dead ends: 118 [2023-11-23 06:34:49,721 INFO L226 Difference]: Without dead ends: 111 [2023-11-23 06:34:49,722 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 145 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=115, Invalid=535, Unknown=0, NotChecked=0, Total=650 [2023-11-23 06:34:49,722 INFO L413 NwaCegarLoop]: 102 mSDtfsCounter, 30 mSDsluCounter, 1185 mSDsCounter, 0 mSdLazyCounter, 437 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 1287 SdHoareTripleChecker+Invalid, 442 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 437 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2023-11-23 06:34:49,722 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 1287 Invalid, 442 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 437 Invalid, 0 Unknown, 0 Unchecked, 1.6s Time] [2023-11-23 06:34:49,723 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2023-11-23 06:34:49,733 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 108. [2023-11-23 06:34:49,736 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 71 states have (on average 1.2394366197183098) internal successors, (88), 72 states have internal predecessors, (88), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (22), 21 states have call predecessors, (22), 21 states have call successors, (22) [2023-11-23 06:34:49,737 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 132 transitions. [2023-11-23 06:34:49,737 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 132 transitions. Word has length 81 [2023-11-23 06:34:49,738 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 06:34:49,738 INFO L495 AbstractCegarLoop]: Abstraction has 108 states and 132 transitions. [2023-11-23 06:34:49,738 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 3.388888888888889) internal successors, (61), 17 states have internal predecessors, (61), 5 states have call successors, (14), 3 states have call predecessors, (14), 6 states have return successors, (15), 5 states have call predecessors, (15), 4 states have call successors, (15) [2023-11-23 06:34:49,738 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 132 transitions. [2023-11-23 06:34:49,742 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2023-11-23 06:34:49,742 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:34:49,742 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 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, 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-23 06:34:49,761 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-23 06:34:49,958 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:49,958 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:34:49,959 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:34:49,959 INFO L85 PathProgramCache]: Analyzing trace with hash 1319902129, now seen corresponding path program 1 times [2023-11-23 06:34:49,959 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:34:49,959 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [391718830] [2023-11-23 06:34:49,959 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:49,959 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:34:50,019 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 06:34:50,034 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [297055641] [2023-11-23 06:34:50,034 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:50,034 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:50,035 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 06:34:50,035 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 06:34:50,058 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-23 06:34:50,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:50,424 INFO L262 TraceCheckSpWp]: Trace formula consists of 2236 conjuncts, 33 conjunts are in the unsatisfiable core [2023-11-23 06:34:50,427 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 06:34:50,472 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2023-11-23 06:34:50,473 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 06:34:50,583 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2023-11-23 06:34:50,583 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 06:34:50,583 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [391718830] [2023-11-23 06:34:50,583 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 06:34:50,583 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [297055641] [2023-11-23 06:34:50,584 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [297055641] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 06:34:50,584 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 06:34:50,584 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5] total 10 [2023-11-23 06:34:50,584 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [589152398] [2023-11-23 06:34:50,584 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 06:34:50,585 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-23 06:34:50,585 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 06:34:50,586 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-23 06:34:50,586 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2023-11-23 06:34:50,586 INFO L87 Difference]: Start difference. First operand 108 states and 132 transitions. Second operand has 10 states, 8 states have (on average 7.375) internal successors, (59), 10 states have internal predecessors, (59), 2 states have call successors, (14), 2 states have call predecessors, (14), 5 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2023-11-23 06:34:51,113 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 06:34:51,114 INFO L93 Difference]: Finished difference Result 133 states and 162 transitions. [2023-11-23 06:34:51,114 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-11-23 06:34:51,114 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 7.375) internal successors, (59), 10 states have internal predecessors, (59), 2 states have call successors, (14), 2 states have call predecessors, (14), 5 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) Word has length 83 [2023-11-23 06:34:51,114 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 06:34:51,115 INFO L225 Difference]: With dead ends: 133 [2023-11-23 06:34:51,115 INFO L226 Difference]: Without dead ends: 114 [2023-11-23 06:34:51,115 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 167 GetRequests, 156 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=110, Unknown=0, NotChecked=0, Total=156 [2023-11-23 06:34:51,115 INFO L413 NwaCegarLoop]: 103 mSDtfsCounter, 10 mSDsluCounter, 604 mSDsCounter, 0 mSdLazyCounter, 123 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 707 SdHoareTripleChecker+Invalid, 127 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 123 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-23 06:34:51,116 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 707 Invalid, 127 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 123 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-23 06:34:51,116 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2023-11-23 06:34:51,123 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 111. [2023-11-23 06:34:51,124 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 74 states have (on average 1.2297297297297298) internal successors, (91), 75 states have internal predecessors, (91), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (22), 21 states have call predecessors, (22), 21 states have call successors, (22) [2023-11-23 06:34:51,124 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 135 transitions. [2023-11-23 06:34:51,124 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 135 transitions. Word has length 83 [2023-11-23 06:34:51,125 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 06:34:51,125 INFO L495 AbstractCegarLoop]: Abstraction has 111 states and 135 transitions. [2023-11-23 06:34:51,125 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 7.375) internal successors, (59), 10 states have internal predecessors, (59), 2 states have call successors, (14), 2 states have call predecessors, (14), 5 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2023-11-23 06:34:51,125 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 135 transitions. [2023-11-23 06:34:51,126 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2023-11-23 06:34:51,126 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:34:51,126 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 06:34:51,142 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-23 06:34:51,332 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:51,332 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:34:51,333 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:34:51,333 INFO L85 PathProgramCache]: Analyzing trace with hash 1947202994, now seen corresponding path program 2 times [2023-11-23 06:34:51,333 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:34:51,333 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [916078917] [2023-11-23 06:34:51,333 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:51,333 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:34:51,382 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 06:34:51,383 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [194746300] [2023-11-23 06:34:51,383 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-11-23 06:34:51,383 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:51,383 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 06:34:51,384 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 06:34:51,409 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-23 06:34:51,735 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-11-23 06:34:51,735 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 06:34:51,744 INFO L262 TraceCheckSpWp]: Trace formula consists of 2293 conjuncts, 16 conjunts are in the unsatisfiable core [2023-11-23 06:34:51,746 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 06:34:51,791 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 5 proven. 8 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-11-23 06:34:51,792 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 06:34:51,883 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 5 proven. 1 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2023-11-23 06:34:51,883 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 06:34:51,884 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [916078917] [2023-11-23 06:34:51,884 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 06:34:51,884 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [194746300] [2023-11-23 06:34:51,884 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [194746300] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 06:34:51,884 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 06:34:51,884 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 5] total 11 [2023-11-23 06:34:51,884 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [256987450] [2023-11-23 06:34:51,885 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 06:34:51,885 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-11-23 06:34:51,885 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 06:34:51,885 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-11-23 06:34:51,886 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=82, Unknown=0, NotChecked=0, Total=110 [2023-11-23 06:34:51,886 INFO L87 Difference]: Start difference. First operand 111 states and 135 transitions. Second operand has 11 states, 11 states have (on average 5.454545454545454) internal successors, (60), 11 states have internal predecessors, (60), 2 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (14), 2 states have call predecessors, (14), 1 states have call successors, (14) [2023-11-23 06:34:52,242 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 06:34:52,242 INFO L93 Difference]: Finished difference Result 220 states and 268 transitions. [2023-11-23 06:34:52,243 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-11-23 06:34:52,243 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 5.454545454545454) internal successors, (60), 11 states have internal predecessors, (60), 2 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (14), 2 states have call predecessors, (14), 1 states have call successors, (14) Word has length 86 [2023-11-23 06:34:52,243 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 06:34:52,244 INFO L225 Difference]: With dead ends: 220 [2023-11-23 06:34:52,244 INFO L226 Difference]: Without dead ends: 136 [2023-11-23 06:34:52,244 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 176 GetRequests, 163 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2023-11-23 06:34:52,245 INFO L413 NwaCegarLoop]: 105 mSDtfsCounter, 26 mSDsluCounter, 523 mSDsCounter, 0 mSdLazyCounter, 130 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 628 SdHoareTripleChecker+Invalid, 135 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 130 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-23 06:34:52,245 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 628 Invalid, 135 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 130 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-23 06:34:52,246 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2023-11-23 06:34:52,255 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 122. [2023-11-23 06:34:52,256 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 85 states have (on average 1.2588235294117647) internal successors, (107), 86 states have internal predecessors, (107), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (22), 21 states have call predecessors, (22), 21 states have call successors, (22) [2023-11-23 06:34:52,256 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 151 transitions. [2023-11-23 06:34:52,257 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 151 transitions. Word has length 86 [2023-11-23 06:34:52,257 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 06:34:52,257 INFO L495 AbstractCegarLoop]: Abstraction has 122 states and 151 transitions. [2023-11-23 06:34:52,257 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 5.454545454545454) internal successors, (60), 11 states have internal predecessors, (60), 2 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (14), 2 states have call predecessors, (14), 1 states have call successors, (14) [2023-11-23 06:34:52,257 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 151 transitions. [2023-11-23 06:34:52,258 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2023-11-23 06:34:52,258 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:34:52,258 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 06:34:52,274 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-23 06:34:52,474 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:52,474 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:34:52,474 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:34:52,475 INFO L85 PathProgramCache]: Analyzing trace with hash -779702103, now seen corresponding path program 1 times [2023-11-23 06:34:52,475 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:34:52,475 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1185899018] [2023-11-23 06:34:52,475 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:52,475 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:34:52,519 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 06:34:52,519 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1992112856] [2023-11-23 06:34:52,519 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:52,520 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:52,520 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 06:34:52,521 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 06:34:52,561 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-23 06:34:52,913 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:52,922 INFO L262 TraceCheckSpWp]: Trace formula consists of 2296 conjuncts, 15 conjunts are in the unsatisfiable core [2023-11-23 06:34:52,925 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 06:34:52,964 INFO L134 CoverageAnalysis]: Checked inductivity of 43 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2023-11-23 06:34:52,965 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-23 06:34:52,965 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 06:34:52,965 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1185899018] [2023-11-23 06:34:52,965 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 06:34:52,965 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1992112856] [2023-11-23 06:34:52,965 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1992112856] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 06:34:52,966 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 06:34:52,966 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2023-11-23 06:34:52,966 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [559265561] [2023-11-23 06:34:52,966 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 06:34:52,966 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-11-23 06:34:52,966 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 06:34:52,967 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-11-23 06:34:52,967 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2023-11-23 06:34:52,967 INFO L87 Difference]: Start difference. First operand 122 states and 151 transitions. Second operand has 9 states, 7 states have (on average 7.0) internal successors, (49), 7 states have internal predecessors, (49), 3 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2023-11-23 06:34:53,377 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 06:34:53,377 INFO L93 Difference]: Finished difference Result 134 states and 163 transitions. [2023-11-23 06:34:53,378 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-23 06:34:53,378 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 7.0) internal successors, (49), 7 states have internal predecessors, (49), 3 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 86 [2023-11-23 06:34:53,378 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 06:34:53,380 INFO L225 Difference]: With dead ends: 134 [2023-11-23 06:34:53,380 INFO L226 Difference]: Without dead ends: 127 [2023-11-23 06:34:53,380 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2023-11-23 06:34:53,381 INFO L413 NwaCegarLoop]: 100 mSDtfsCounter, 4 mSDsluCounter, 671 mSDsCounter, 0 mSdLazyCounter, 185 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 771 SdHoareTripleChecker+Invalid, 187 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 185 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-23 06:34:53,381 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 771 Invalid, 187 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 185 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-23 06:34:53,381 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2023-11-23 06:34:53,392 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 122. [2023-11-23 06:34:53,393 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 85 states have (on average 1.223529411764706) internal successors, (104), 86 states have internal predecessors, (104), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (22), 21 states have call predecessors, (22), 21 states have call successors, (22) [2023-11-23 06:34:53,394 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 148 transitions. [2023-11-23 06:34:53,394 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 148 transitions. Word has length 86 [2023-11-23 06:34:53,394 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 06:34:53,394 INFO L495 AbstractCegarLoop]: Abstraction has 122 states and 148 transitions. [2023-11-23 06:34:53,394 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 7.0) internal successors, (49), 7 states have internal predecessors, (49), 3 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2023-11-23 06:34:53,395 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 148 transitions. [2023-11-23 06:34:53,395 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2023-11-23 06:34:53,395 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:34:53,396 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 06:34:53,430 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-23 06:34:53,611 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:53,611 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:34:53,611 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:34:53,612 INFO L85 PathProgramCache]: Analyzing trace with hash -1652348772, now seen corresponding path program 3 times [2023-11-23 06:34:53,612 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:34:53,612 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [45819857] [2023-11-23 06:34:53,612 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:53,612 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:34:53,654 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 06:34:53,655 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1149061353] [2023-11-23 06:34:53,655 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-23 06:34:53,655 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:53,655 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 06:34:53,656 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 06:34:53,667 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-23 06:34:54,072 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-23 06:34:54,073 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 06:34:54,080 INFO L262 TraceCheckSpWp]: Trace formula consists of 1920 conjuncts, 6 conjunts are in the unsatisfiable core [2023-11-23 06:34:54,083 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 06:34:54,099 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 24 proven. 0 refuted. 0 times theorem prover too weak. 38 trivial. 0 not checked. [2023-11-23 06:34:54,099 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-23 06:34:54,099 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 06:34:54,100 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [45819857] [2023-11-23 06:34:54,100 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 06:34:54,100 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1149061353] [2023-11-23 06:34:54,100 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1149061353] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 06:34:54,100 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 06:34:54,100 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-23 06:34:54,100 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1202239080] [2023-11-23 06:34:54,101 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 06:34:54,101 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-23 06:34:54,101 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 06:34:54,101 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-23 06:34:54,101 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-23 06:34:54,102 INFO L87 Difference]: Start difference. First operand 122 states and 148 transitions. Second operand has 5 states, 5 states have (on average 10.4) internal successors, (52), 4 states have internal predecessors, (52), 2 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 2 states have call successors, (12) [2023-11-23 06:34:54,247 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 06:34:54,247 INFO L93 Difference]: Finished difference Result 178 states and 214 transitions. [2023-11-23 06:34:54,248 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-23 06:34:54,248 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 10.4) internal successors, (52), 4 states have internal predecessors, (52), 2 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 2 states have call successors, (12) Word has length 92 [2023-11-23 06:34:54,248 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 06:34:54,249 INFO L225 Difference]: With dead ends: 178 [2023-11-23 06:34:54,249 INFO L226 Difference]: Without dead ends: 130 [2023-11-23 06:34:54,249 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 88 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-23 06:34:54,249 INFO L413 NwaCegarLoop]: 112 mSDtfsCounter, 4 mSDsluCounter, 319 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 431 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 06:34:54,250 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 431 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 06:34:54,250 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2023-11-23 06:34:54,258 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 126. [2023-11-23 06:34:54,258 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 126 states, 88 states have (on average 1.2159090909090908) internal successors, (107), 89 states have internal predecessors, (107), 22 states have call successors, (22), 14 states have call predecessors, (22), 15 states have return successors, (23), 22 states have call predecessors, (23), 21 states have call successors, (23) [2023-11-23 06:34:54,259 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 152 transitions. [2023-11-23 06:34:54,259 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 152 transitions. Word has length 92 [2023-11-23 06:34:54,259 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 06:34:54,259 INFO L495 AbstractCegarLoop]: Abstraction has 126 states and 152 transitions. [2023-11-23 06:34:54,259 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 10.4) internal successors, (52), 4 states have internal predecessors, (52), 2 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 2 states have call successors, (12) [2023-11-23 06:34:54,260 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 152 transitions. [2023-11-23 06:34:54,260 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2023-11-23 06:34:54,260 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:34:54,260 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 2, 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, 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-23 06:34:54,276 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-23 06:34:54,474 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:54,475 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:34:54,475 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:34:54,475 INFO L85 PathProgramCache]: Analyzing trace with hash 937275213, now seen corresponding path program 1 times [2023-11-23 06:34:54,475 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:34:54,475 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [478736361] [2023-11-23 06:34:54,475 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:54,475 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:34:54,525 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 06:34:54,525 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [869438628] [2023-11-23 06:34:54,525 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:54,526 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:54,526 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 06:34:54,526 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 06:34:54,548 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-23 06:34:54,899 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:54,906 INFO L262 TraceCheckSpWp]: Trace formula consists of 2396 conjuncts, 7 conjunts are in the unsatisfiable core [2023-11-23 06:34:54,909 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 06:34:54,948 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 27 proven. 0 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2023-11-23 06:34:54,949 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-23 06:34:54,949 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 06:34:54,949 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [478736361] [2023-11-23 06:34:54,949 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 06:34:54,949 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [869438628] [2023-11-23 06:34:54,949 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [869438628] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 06:34:54,949 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 06:34:54,950 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2023-11-23 06:34:54,951 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2146882548] [2023-11-23 06:34:54,952 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 06:34:54,952 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-23 06:34:54,952 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 06:34:54,952 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-23 06:34:54,953 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-23 06:34:54,953 INFO L87 Difference]: Start difference. First operand 126 states and 152 transitions. Second operand has 6 states, 6 states have (on average 9.333333333333334) internal successors, (56), 6 states have internal predecessors, (56), 4 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2023-11-23 06:34:55,160 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 06:34:55,160 INFO L93 Difference]: Finished difference Result 175 states and 207 transitions. [2023-11-23 06:34:55,160 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-23 06:34:55,161 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 9.333333333333334) internal successors, (56), 6 states have internal predecessors, (56), 4 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) Word has length 98 [2023-11-23 06:34:55,162 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 06:34:55,162 INFO L225 Difference]: With dead ends: 175 [2023-11-23 06:34:55,162 INFO L226 Difference]: Without dead ends: 124 [2023-11-23 06:34:55,163 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 94 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2023-11-23 06:34:55,163 INFO L413 NwaCegarLoop]: 95 mSDtfsCounter, 45 mSDsluCounter, 317 mSDsCounter, 0 mSdLazyCounter, 106 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 412 SdHoareTripleChecker+Invalid, 115 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 106 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-23 06:34:55,164 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [50 Valid, 412 Invalid, 115 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 106 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-23 06:34:55,165 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2023-11-23 06:34:55,172 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 124. [2023-11-23 06:34:55,172 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 124 states, 87 states have (on average 1.206896551724138) internal successors, (105), 87 states have internal predecessors, (105), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (22), 22 states have call predecessors, (22), 21 states have call successors, (22) [2023-11-23 06:34:55,173 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 149 transitions. [2023-11-23 06:34:55,173 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 149 transitions. Word has length 98 [2023-11-23 06:34:55,173 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 06:34:55,173 INFO L495 AbstractCegarLoop]: Abstraction has 124 states and 149 transitions. [2023-11-23 06:34:55,174 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 9.333333333333334) internal successors, (56), 6 states have internal predecessors, (56), 4 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2023-11-23 06:34:55,174 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 149 transitions. [2023-11-23 06:34:55,176 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2023-11-23 06:34:55,176 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:34:55,176 INFO L195 NwaCegarLoop]: trace histogram [8, 8, 4, 4, 4, 4, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 06:34:55,193 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-23 06:34:55,394 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-11-23 06:34:55,394 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:34:55,395 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:34:55,395 INFO L85 PathProgramCache]: Analyzing trace with hash -1945497413, now seen corresponding path program 1 times [2023-11-23 06:34:55,395 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:34:55,395 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [303800847] [2023-11-23 06:34:55,395 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:55,395 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:34:55,446 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 06:34:55,446 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1447722907] [2023-11-23 06:34:55,446 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:55,446 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:55,447 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 06:34:55,447 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 06:34:55,471 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-23 06:34:56,092 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:56,100 INFO L262 TraceCheckSpWp]: Trace formula consists of 2339 conjuncts, 17 conjunts are in the unsatisfiable core [2023-11-23 06:34:56,103 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 06:34:56,160 INFO L134 CoverageAnalysis]: Checked inductivity of 111 backedges. 57 proven. 16 refuted. 0 times theorem prover too weak. 38 trivial. 0 not checked. [2023-11-23 06:34:56,161 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 06:34:56,395 INFO L134 CoverageAnalysis]: Checked inductivity of 111 backedges. 0 proven. 60 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2023-11-23 06:34:56,396 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 06:34:56,396 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [303800847] [2023-11-23 06:34:56,396 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 06:34:56,396 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1447722907] [2023-11-23 06:34:56,396 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1447722907] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 06:34:56,396 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 06:34:56,396 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2023-11-23 06:34:56,397 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [72786693] [2023-11-23 06:34:56,397 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 06:34:56,397 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-23 06:34:56,398 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 06:34:56,398 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-23 06:34:56,398 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=121, Unknown=0, NotChecked=0, Total=182 [2023-11-23 06:34:56,399 INFO L87 Difference]: Start difference. First operand 124 states and 149 transitions. Second operand has 14 states, 14 states have (on average 5.785714285714286) internal successors, (81), 14 states have internal predecessors, (81), 2 states have call successors, (16), 2 states have call predecessors, (16), 4 states have return successors, (16), 2 states have call predecessors, (16), 2 states have call successors, (16) [2023-11-23 06:34:57,008 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 06:34:57,008 INFO L93 Difference]: Finished difference Result 253 states and 307 transitions. [2023-11-23 06:34:57,009 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-11-23 06:34:57,009 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 5.785714285714286) internal successors, (81), 14 states have internal predecessors, (81), 2 states have call successors, (16), 2 states have call predecessors, (16), 4 states have return successors, (16), 2 states have call predecessors, (16), 2 states have call successors, (16) Word has length 100 [2023-11-23 06:34:57,009 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 06:34:57,010 INFO L225 Difference]: With dead ends: 253 [2023-11-23 06:34:57,010 INFO L226 Difference]: Without dead ends: 166 [2023-11-23 06:34:57,011 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 207 GetRequests, 190 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=131, Invalid=211, Unknown=0, NotChecked=0, Total=342 [2023-11-23 06:34:57,011 INFO L413 NwaCegarLoop]: 113 mSDtfsCounter, 67 mSDsluCounter, 577 mSDsCounter, 0 mSdLazyCounter, 192 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 67 SdHoareTripleChecker+Valid, 690 SdHoareTripleChecker+Invalid, 196 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 192 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-23 06:34:57,012 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [67 Valid, 690 Invalid, 196 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 192 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-23 06:34:57,012 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 166 states. [2023-11-23 06:34:57,033 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 166 to 148. [2023-11-23 06:34:57,034 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 111 states have (on average 1.2162162162162162) internal successors, (135), 111 states have internal predecessors, (135), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (22), 22 states have call predecessors, (22), 21 states have call successors, (22) [2023-11-23 06:34:57,035 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 179 transitions. [2023-11-23 06:34:57,035 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 179 transitions. Word has length 100 [2023-11-23 06:34:57,036 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 06:34:57,036 INFO L495 AbstractCegarLoop]: Abstraction has 148 states and 179 transitions. [2023-11-23 06:34:57,036 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 5.785714285714286) internal successors, (81), 14 states have internal predecessors, (81), 2 states have call successors, (16), 2 states have call predecessors, (16), 4 states have return successors, (16), 2 states have call predecessors, (16), 2 states have call successors, (16) [2023-11-23 06:34:57,036 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 179 transitions. [2023-11-23 06:34:57,037 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2023-11-23 06:34:57,037 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:34:57,038 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 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, 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-23 06:34:57,056 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2023-11-23 06:34:57,252 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:57,252 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:34:57,253 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:34:57,253 INFO L85 PathProgramCache]: Analyzing trace with hash -1671360575, now seen corresponding path program 1 times [2023-11-23 06:34:57,253 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:34:57,253 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [819880012] [2023-11-23 06:34:57,253 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:57,253 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:34:57,308 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 06:34:57,309 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [178325134] [2023-11-23 06:34:57,309 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:57,309 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:57,309 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 06:34:57,321 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 06:34:57,349 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-11-23 06:34:57,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 06:34:57,814 INFO L262 TraceCheckSpWp]: Trace formula consists of 2625 conjuncts, 28 conjunts are in the unsatisfiable core [2023-11-23 06:34:57,818 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 06:34:57,857 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 24 proven. 10 refuted. 0 times theorem prover too weak. 141 trivial. 0 not checked. [2023-11-23 06:34:57,858 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 06:34:58,008 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 165 trivial. 0 not checked. [2023-11-23 06:34:58,009 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 06:34:58,009 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [819880012] [2023-11-23 06:34:58,009 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 06:34:58,009 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [178325134] [2023-11-23 06:34:58,009 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [178325134] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 06:34:58,009 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 06:34:58,009 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2023-11-23 06:34:58,010 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1008645553] [2023-11-23 06:34:58,010 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 06:34:58,010 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-23 06:34:58,010 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 06:34:58,011 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-23 06:34:58,011 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=121, Unknown=0, NotChecked=0, Total=182 [2023-11-23 06:34:58,012 INFO L87 Difference]: Start difference. First operand 148 states and 179 transitions. Second operand has 14 states, 12 states have (on average 5.166666666666667) internal successors, (62), 14 states have internal predecessors, (62), 2 states have call successors, (15), 2 states have call predecessors, (15), 4 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2023-11-23 06:34:58,534 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 06:34:58,534 INFO L93 Difference]: Finished difference Result 190 states and 227 transitions. [2023-11-23 06:34:58,535 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-11-23 06:34:58,535 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 5.166666666666667) internal successors, (62), 14 states have internal predecessors, (62), 2 states have call successors, (15), 2 states have call predecessors, (15), 4 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) Word has length 123 [2023-11-23 06:34:58,535 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 06:34:58,536 INFO L225 Difference]: With dead ends: 190 [2023-11-23 06:34:58,536 INFO L226 Difference]: Without dead ends: 154 [2023-11-23 06:34:58,536 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 249 GetRequests, 232 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=131, Invalid=211, Unknown=0, NotChecked=0, Total=342 [2023-11-23 06:34:58,537 INFO L413 NwaCegarLoop]: 107 mSDtfsCounter, 1 mSDsluCounter, 632 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 739 SdHoareTripleChecker+Invalid, 127 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-23 06:34:58,537 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 739 Invalid, 127 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-23 06:34:58,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 154 states. [2023-11-23 06:34:58,549 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 154 to 154. [2023-11-23 06:34:58,549 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 117 states have (on average 1.205128205128205) internal successors, (141), 117 states have internal predecessors, (141), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (22), 22 states have call predecessors, (22), 21 states have call successors, (22) [2023-11-23 06:34:58,550 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 185 transitions. [2023-11-23 06:34:58,550 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 185 transitions. Word has length 123 [2023-11-23 06:34:58,550 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 06:34:58,550 INFO L495 AbstractCegarLoop]: Abstraction has 154 states and 185 transitions. [2023-11-23 06:34:58,551 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 5.166666666666667) internal successors, (62), 14 states have internal predecessors, (62), 2 states have call successors, (15), 2 states have call predecessors, (15), 4 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2023-11-23 06:34:58,551 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 185 transitions. [2023-11-23 06:34:58,552 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2023-11-23 06:34:58,552 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:34:58,552 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 2, 2, 2, 2, 2, 2, 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, 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-23 06:34:58,568 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2023-11-23 06:34:58,769 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-11-23 06:34:58,769 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:34:58,770 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:34:58,770 INFO L85 PathProgramCache]: Analyzing trace with hash 153253537, now seen corresponding path program 2 times [2023-11-23 06:34:58,770 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:34:58,770 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [517653464] [2023-11-23 06:34:58,770 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:34:58,770 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:34:58,832 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 06:34:58,832 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1617912] [2023-11-23 06:34:58,832 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-11-23 06:34:58,833 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:34:58,833 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 06:34:58,847 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 06:34:58,871 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-11-23 06:35:00,313 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-11-23 06:35:00,313 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 06:35:00,325 INFO L262 TraceCheckSpWp]: Trace formula consists of 2739 conjuncts, 66 conjunts are in the unsatisfiable core [2023-11-23 06:35:00,331 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 06:35:00,461 INFO L134 CoverageAnalysis]: Checked inductivity of 220 backedges. 24 proven. 55 refuted. 0 times theorem prover too weak. 141 trivial. 0 not checked. [2023-11-23 06:35:00,461 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 06:35:01,037 INFO L134 CoverageAnalysis]: Checked inductivity of 220 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 165 trivial. 0 not checked. [2023-11-23 06:35:01,037 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 06:35:01,037 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [517653464] [2023-11-23 06:35:01,037 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 06:35:01,037 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1617912] [2023-11-23 06:35:01,037 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1617912] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 06:35:01,037 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 06:35:01,038 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 14] total 27 [2023-11-23 06:35:01,038 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [874081836] [2023-11-23 06:35:01,038 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 06:35:01,038 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2023-11-23 06:35:01,038 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 06:35:01,039 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2023-11-23 06:35:01,039 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=195, Invalid=507, Unknown=0, NotChecked=0, Total=702 [2023-11-23 06:35:01,039 INFO L87 Difference]: Start difference. First operand 154 states and 185 transitions. Second operand has 27 states, 25 states have (on average 3.24) internal successors, (81), 27 states have internal predecessors, (81), 3 states have call successors, (19), 2 states have call predecessors, (19), 4 states have return successors, (18), 3 states have call predecessors, (18), 3 states have call successors, (18) [2023-11-23 06:35:03,969 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 06:35:03,969 INFO L93 Difference]: Finished difference Result 202 states and 245 transitions. [2023-11-23 06:35:03,970 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2023-11-23 06:35:03,970 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 25 states have (on average 3.24) internal successors, (81), 27 states have internal predecessors, (81), 3 states have call successors, (19), 2 states have call predecessors, (19), 4 states have return successors, (18), 3 states have call predecessors, (18), 3 states have call successors, (18) Word has length 129 [2023-11-23 06:35:03,970 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 06:35:03,971 INFO L225 Difference]: With dead ends: 202 [2023-11-23 06:35:03,971 INFO L226 Difference]: Without dead ends: 166 [2023-11-23 06:35:03,972 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 268 GetRequests, 231 SyntacticMatches, 0 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=508, Invalid=974, Unknown=0, NotChecked=0, Total=1482 [2023-11-23 06:35:03,972 INFO L413 NwaCegarLoop]: 103 mSDtfsCounter, 7 mSDsluCounter, 1199 mSDsCounter, 0 mSdLazyCounter, 358 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 1302 SdHoareTripleChecker+Invalid, 369 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 358 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2023-11-23 06:35:03,972 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 1302 Invalid, 369 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 358 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2023-11-23 06:35:03,973 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 166 states. [2023-11-23 06:35:03,985 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 166 to 166. [2023-11-23 06:35:03,985 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 166 states, 129 states have (on average 1.186046511627907) internal successors, (153), 129 states have internal predecessors, (153), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (22), 22 states have call predecessors, (22), 21 states have call successors, (22) [2023-11-23 06:35:03,986 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 166 states to 166 states and 197 transitions. [2023-11-23 06:35:03,986 INFO L78 Accepts]: Start accepts. Automaton has 166 states and 197 transitions. Word has length 129 [2023-11-23 06:35:03,986 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 06:35:03,986 INFO L495 AbstractCegarLoop]: Abstraction has 166 states and 197 transitions. [2023-11-23 06:35:03,987 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 25 states have (on average 3.24) internal successors, (81), 27 states have internal predecessors, (81), 3 states have call successors, (19), 2 states have call predecessors, (19), 4 states have return successors, (18), 3 states have call predecessors, (18), 3 states have call successors, (18) [2023-11-23 06:35:03,987 INFO L276 IsEmpty]: Start isEmpty. Operand 166 states and 197 transitions. [2023-11-23 06:35:03,988 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 142 [2023-11-23 06:35:03,988 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:35:03,988 INFO L195 NwaCegarLoop]: trace histogram [22, 11, 10, 4, 4, 4, 2, 2, 2, 2, 2, 2, 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, 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-23 06:35:04,010 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-11-23 06:35:04,208 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-11-23 06:35:04,209 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:35:04,209 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:35:04,209 INFO L85 PathProgramCache]: Analyzing trace with hash 1622232161, now seen corresponding path program 3 times [2023-11-23 06:35:04,209 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:35:04,209 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1168878547] [2023-11-23 06:35:04,209 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:35:04,209 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:35:04,264 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 06:35:04,264 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [64294549] [2023-11-23 06:35:04,264 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-23 06:35:04,264 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:35:04,265 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 06:35:04,281 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 06:35:04,283 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-11-23 06:37:05,617 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2023-11-23 06:37:05,618 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 06:37:05,652 INFO L262 TraceCheckSpWp]: Trace formula consists of 2929 conjuncts, 59 conjunts are in the unsatisfiable core [2023-11-23 06:37:05,656 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 06:37:06,231 INFO L134 CoverageAnalysis]: Checked inductivity of 418 backedges. 21 proven. 174 refuted. 0 times theorem prover too weak. 223 trivial. 0 not checked. [2023-11-23 06:37:06,232 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 06:37:06,783 INFO L134 CoverageAnalysis]: Checked inductivity of 418 backedges. 23 proven. 100 refuted. 0 times theorem prover too weak. 295 trivial. 0 not checked. [2023-11-23 06:37:06,783 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 06:37:06,783 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1168878547] [2023-11-23 06:37:06,783 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 06:37:06,783 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [64294549] [2023-11-23 06:37:06,784 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [64294549] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 06:37:06,784 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 06:37:06,784 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 14] total 37 [2023-11-23 06:37:06,784 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2081127464] [2023-11-23 06:37:06,784 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 06:37:06,784 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 37 states [2023-11-23 06:37:06,784 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 06:37:06,785 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2023-11-23 06:37:06,785 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=215, Invalid=1117, Unknown=0, NotChecked=0, Total=1332 [2023-11-23 06:37:06,786 INFO L87 Difference]: Start difference. First operand 166 states and 197 transitions. Second operand has 37 states, 35 states have (on average 3.0285714285714285) internal successors, (106), 35 states have internal predecessors, (106), 3 states have call successors, (15), 2 states have call predecessors, (15), 7 states have return successors, (18), 4 states have call predecessors, (18), 2 states have call successors, (18) [2023-11-23 06:37:12,374 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 06:37:12,374 INFO L93 Difference]: Finished difference Result 377 states and 457 transitions. [2023-11-23 06:37:12,374 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2023-11-23 06:37:12,375 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 35 states have (on average 3.0285714285714285) internal successors, (106), 35 states have internal predecessors, (106), 3 states have call successors, (15), 2 states have call predecessors, (15), 7 states have return successors, (18), 4 states have call predecessors, (18), 2 states have call successors, (18) Word has length 141 [2023-11-23 06:37:12,376 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 06:37:12,379 INFO L225 Difference]: With dead ends: 377 [2023-11-23 06:37:12,379 INFO L226 Difference]: Without dead ends: 260 [2023-11-23 06:37:12,381 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 329 GetRequests, 256 SyntacticMatches, 0 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 847 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=1126, Invalid=4424, Unknown=0, NotChecked=0, Total=5550 [2023-11-23 06:37:12,382 INFO L413 NwaCegarLoop]: 115 mSDtfsCounter, 327 mSDsluCounter, 2550 mSDsCounter, 0 mSdLazyCounter, 1479 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 330 SdHoareTripleChecker+Valid, 2665 SdHoareTripleChecker+Invalid, 1487 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 1479 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2023-11-23 06:37:12,384 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [330 Valid, 2665 Invalid, 1487 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 1479 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2023-11-23 06:37:12,384 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 260 states. [2023-11-23 06:37:12,420 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 260 to 214. [2023-11-23 06:37:12,421 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 214 states, 177 states have (on average 1.2033898305084745) internal successors, (213), 177 states have internal predecessors, (213), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (22), 22 states have call predecessors, (22), 21 states have call successors, (22) [2023-11-23 06:37:12,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 214 states to 214 states and 257 transitions. [2023-11-23 06:37:12,424 INFO L78 Accepts]: Start accepts. Automaton has 214 states and 257 transitions. Word has length 141 [2023-11-23 06:37:12,425 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 06:37:12,425 INFO L495 AbstractCegarLoop]: Abstraction has 214 states and 257 transitions. [2023-11-23 06:37:12,425 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 37 states, 35 states have (on average 3.0285714285714285) internal successors, (106), 35 states have internal predecessors, (106), 3 states have call successors, (15), 2 states have call predecessors, (15), 7 states have return successors, (18), 4 states have call predecessors, (18), 2 states have call successors, (18) [2023-11-23 06:37:12,426 INFO L276 IsEmpty]: Start isEmpty. Operand 214 states and 257 transitions. [2023-11-23 06:37:12,428 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 166 [2023-11-23 06:37:12,428 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:37:12,428 INFO L195 NwaCegarLoop]: trace histogram [23, 22, 22, 4, 4, 4, 2, 2, 2, 2, 2, 2, 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, 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-23 06:37:12,474 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-11-23 06:37:12,644 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2023-11-23 06:37:12,644 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:37:12,645 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:37:12,645 INFO L85 PathProgramCache]: Analyzing trace with hash 784543241, now seen corresponding path program 4 times [2023-11-23 06:37:12,645 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:37:12,645 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [694592494] [2023-11-23 06:37:12,645 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:37:12,645 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:37:12,716 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 06:37:12,716 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1821899846] [2023-11-23 06:37:12,716 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-23 06:37:12,717 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:37:12,717 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 06:37:12,717 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 06:37:12,719 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-11-23 06:37:22,184 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-23 06:37:22,184 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 06:37:22,204 INFO L262 TraceCheckSpWp]: Trace formula consists of 3051 conjuncts, 104 conjunts are in the unsatisfiable core [2023-11-23 06:37:22,208 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 06:37:22,456 INFO L134 CoverageAnalysis]: Checked inductivity of 826 backedges. 48 proven. 253 refuted. 0 times theorem prover too weak. 525 trivial. 0 not checked. [2023-11-23 06:37:22,456 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 06:37:23,720 INFO L134 CoverageAnalysis]: Checked inductivity of 826 backedges. 47 proven. 484 refuted. 0 times theorem prover too weak. 295 trivial. 0 not checked. [2023-11-23 06:37:23,721 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 06:37:23,721 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [694592494] [2023-11-23 06:37:23,721 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 06:37:23,721 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1821899846] [2023-11-23 06:37:23,721 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1821899846] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 06:37:23,721 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 06:37:23,721 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 26] total 50 [2023-11-23 06:37:23,721 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [59160995] [2023-11-23 06:37:23,721 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 06:37:23,722 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2023-11-23 06:37:23,723 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 06:37:23,723 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2023-11-23 06:37:23,724 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=120, Invalid=2330, Unknown=0, NotChecked=0, Total=2450 [2023-11-23 06:37:23,724 INFO L87 Difference]: Start difference. First operand 214 states and 257 transitions. Second operand has 50 states, 49 states have (on average 2.5510204081632653) internal successors, (125), 50 states have internal predecessors, (125), 2 states have call successors, (15), 2 states have call predecessors, (15), 4 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2023-11-23 06:37:44,387 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 06:37:44,388 INFO L93 Difference]: Finished difference Result 399 states and 457 transitions. [2023-11-23 06:37:44,388 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 50 states. [2023-11-23 06:37:44,388 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 49 states have (on average 2.5510204081632653) internal successors, (125), 50 states have internal predecessors, (125), 2 states have call successors, (15), 2 states have call predecessors, (15), 4 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) Word has length 165 [2023-11-23 06:37:44,389 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 06:37:44,390 INFO L225 Difference]: With dead ends: 399 [2023-11-23 06:37:44,390 INFO L226 Difference]: Without dead ends: 263 [2023-11-23 06:37:44,391 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 372 GetRequests, 301 SyntacticMatches, 0 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 253 ImplicationChecksByTransitivity, 18.4s TimeCoverageRelationStatistics Valid=696, Invalid=4560, Unknown=0, NotChecked=0, Total=5256 [2023-11-23 06:37:44,391 INFO L413 NwaCegarLoop]: 105 mSDtfsCounter, 576 mSDsluCounter, 4820 mSDsCounter, 0 mSdLazyCounter, 1777 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 576 SdHoareTripleChecker+Valid, 4925 SdHoareTripleChecker+Invalid, 1801 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 1777 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.3s IncrementalHoareTripleChecker+Time [2023-11-23 06:37:44,392 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [576 Valid, 4925 Invalid, 1801 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 1777 Invalid, 0 Unknown, 0 Unchecked, 3.3s Time] [2023-11-23 06:37:44,393 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 263 states. [2023-11-23 06:37:44,423 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 263 to 219. [2023-11-23 06:37:44,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 219 states, 182 states have (on average 1.2032967032967032) internal successors, (219), 182 states have internal predecessors, (219), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (22), 22 states have call predecessors, (22), 21 states have call successors, (22) [2023-11-23 06:37:44,424 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 219 states to 219 states and 263 transitions. [2023-11-23 06:37:44,424 INFO L78 Accepts]: Start accepts. Automaton has 219 states and 263 transitions. Word has length 165 [2023-11-23 06:37:44,425 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 06:37:44,425 INFO L495 AbstractCegarLoop]: Abstraction has 219 states and 263 transitions. [2023-11-23 06:37:44,425 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 50 states, 49 states have (on average 2.5510204081632653) internal successors, (125), 50 states have internal predecessors, (125), 2 states have call successors, (15), 2 states have call predecessors, (15), 4 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2023-11-23 06:37:44,425 INFO L276 IsEmpty]: Start isEmpty. Operand 219 states and 263 transitions. [2023-11-23 06:37:44,426 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 169 [2023-11-23 06:37:44,426 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 06:37:44,426 INFO L195 NwaCegarLoop]: trace histogram [24, 23, 23, 4, 4, 4, 2, 2, 2, 2, 2, 2, 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, 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-23 06:37:44,462 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-11-23 06:37:44,640 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-11-23 06:37:44,640 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 06:37:44,641 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 06:37:44,641 INFO L85 PathProgramCache]: Analyzing trace with hash 73895316, now seen corresponding path program 5 times [2023-11-23 06:37:44,641 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 06:37:44,641 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [92946852] [2023-11-23 06:37:44,641 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 06:37:44,641 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 06:37:44,728 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 06:37:44,728 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [774705935] [2023-11-23 06:37:44,728 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2023-11-23 06:37:44,728 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 06:37:44,728 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 06:37:44,729 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 06:37:44,731 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process Killed by 15