./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/ldv-sets/test_mutex_unbounded-2.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version b5237d83 Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/config/TaipanReach.xml -i ../../sv-benchmarks/c/ldv-sets/test_mutex_unbounded-2.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 52ed361cdf08860b8c7c7d564ef95393de2d3a38663ac135cf0da9ded1f39b3f --- Real Ultimate output --- [0.001s][warning][os,container] Duplicate cpuset controllers detected. Picking /sys/fs/cgroup/cpuset, skipping /sys/fs/cgroup/cpuset. This is Ultimate 0.2.2-dev-b5237d8 [2022-11-22 02:25:21,314 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-11-22 02:25:21,317 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-11-22 02:25:21,357 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-11-22 02:25:21,358 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-11-22 02:25:21,359 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-11-22 02:25:21,360 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-11-22 02:25:21,361 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-11-22 02:25:21,362 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-11-22 02:25:21,363 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-11-22 02:25:21,364 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-11-22 02:25:21,366 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-11-22 02:25:21,366 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-11-22 02:25:21,367 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-11-22 02:25:21,369 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-11-22 02:25:21,370 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-11-22 02:25:21,371 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-11-22 02:25:21,372 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-11-22 02:25:21,374 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-11-22 02:25:21,376 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-11-22 02:25:21,378 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-11-22 02:25:21,379 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-11-22 02:25:21,381 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-11-22 02:25:21,382 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-11-22 02:25:21,386 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-11-22 02:25:21,386 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-11-22 02:25:21,387 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-11-22 02:25:21,388 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-11-22 02:25:21,388 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-11-22 02:25:21,389 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-11-22 02:25:21,390 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-11-22 02:25:21,391 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-11-22 02:25:21,392 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-11-22 02:25:21,393 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-11-22 02:25:21,394 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-11-22 02:25:21,394 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-11-22 02:25:21,395 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-11-22 02:25:21,395 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-11-22 02:25:21,396 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-11-22 02:25:21,397 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-11-22 02:25:21,398 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-11-22 02:25:21,401 INFO L101 SettingsManager]: Beginning loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/config/svcomp-Reach-32bit-Taipan_Default.epf [2022-11-22 02:25:21,445 INFO L113 SettingsManager]: Loading preferences was successful [2022-11-22 02:25:21,446 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-11-22 02:25:21,447 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-11-22 02:25:21,447 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-11-22 02:25:21,448 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-11-22 02:25:21,448 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-11-22 02:25:21,449 INFO L138 SettingsManager]: * User list type=DISABLED [2022-11-22 02:25:21,449 INFO L136 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2022-11-22 02:25:21,449 INFO L138 SettingsManager]: * Explicit value domain=true [2022-11-22 02:25:21,449 INFO L138 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2022-11-22 02:25:21,450 INFO L138 SettingsManager]: * Octagon Domain=false [2022-11-22 02:25:21,451 INFO L138 SettingsManager]: * Abstract domain=CompoundDomain [2022-11-22 02:25:21,451 INFO L138 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2022-11-22 02:25:21,451 INFO L138 SettingsManager]: * Use the RCFG-of-the-future interface=true [2022-11-22 02:25:21,451 INFO L138 SettingsManager]: * Interval Domain=false [2022-11-22 02:25:21,452 INFO L136 SettingsManager]: Preferences of Sifa differ from their defaults: [2022-11-22 02:25:21,452 INFO L138 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2022-11-22 02:25:21,452 INFO L138 SettingsManager]: * Simplification Technique=POLY_PAC [2022-11-22 02:25:21,453 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-11-22 02:25:21,453 INFO L138 SettingsManager]: * sizeof long=4 [2022-11-22 02:25:21,453 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-11-22 02:25:21,453 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-11-22 02:25:21,454 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-11-22 02:25:21,454 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-11-22 02:25:21,454 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-11-22 02:25:21,454 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-11-22 02:25:21,455 INFO L138 SettingsManager]: * sizeof long double=12 [2022-11-22 02:25:21,455 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-11-22 02:25:21,455 INFO L138 SettingsManager]: * Use constant arrays=true [2022-11-22 02:25:21,455 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-11-22 02:25:21,455 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-11-22 02:25:21,456 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-11-22 02:25:21,456 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-11-22 02:25:21,456 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-11-22 02:25:21,457 INFO L138 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2022-11-22 02:25:21,457 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-11-22 02:25:21,457 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-11-22 02:25:21,457 INFO L138 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2022-11-22 02:25:21,457 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-11-22 02:25:21,457 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-11-22 02:25:21,458 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-11-22 02:25:21,459 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml 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 -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 52ed361cdf08860b8c7c7d564ef95393de2d3a38663ac135cf0da9ded1f39b3f [2022-11-22 02:25:21,783 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-11-22 02:25:21,812 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-11-22 02:25:21,817 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-11-22 02:25:21,818 INFO L271 PluginConnector]: Initializing CDTParser... [2022-11-22 02:25:21,819 INFO L275 PluginConnector]: CDTParser initialized [2022-11-22 02:25:21,820 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/../../sv-benchmarks/c/ldv-sets/test_mutex_unbounded-2.i [2022-11-22 02:25:24,981 INFO L500 CDTParser]: Created temporary CDT project at NULL [2022-11-22 02:25:25,291 INFO L351 CDTParser]: Found 1 translation units. [2022-11-22 02:25:25,291 INFO L172 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-2.i [2022-11-22 02:25:25,310 INFO L394 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/data/a5282b8ed/148ffad939d4465c8be911a99d59273d/FLAG0780e78ee [2022-11-22 02:25:25,325 INFO L402 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/data/a5282b8ed/148ffad939d4465c8be911a99d59273d [2022-11-22 02:25:25,328 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-11-22 02:25:25,329 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-11-22 02:25:25,331 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-11-22 02:25:25,331 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-11-22 02:25:25,337 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-11-22 02:25:25,338 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.11 02:25:25" (1/1) ... [2022-11-22 02:25:25,339 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@37965ff6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 02:25:25, skipping insertion in model container [2022-11-22 02:25:25,340 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.11 02:25:25" (1/1) ... [2022-11-22 02:25:25,348 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-11-22 02:25:25,386 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-11-22 02:25:25,781 WARN L237 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-2.i[26271,26284] [2022-11-22 02:25:25,790 WARN L237 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-2.i[26396,26409] [2022-11-22 02:25:25,792 WARN L237 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-2.i[26511,26524] [2022-11-22 02:25:25,803 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-11-22 02:25:25,813 INFO L203 MainTranslator]: Completed pre-run [2022-11-22 02:25:25,857 WARN L237 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-2.i[26271,26284] [2022-11-22 02:25:25,858 WARN L237 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-2.i[26396,26409] [2022-11-22 02:25:25,859 WARN L237 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-2.i[26511,26524] [2022-11-22 02:25:25,866 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-11-22 02:25:25,891 INFO L208 MainTranslator]: Completed translation [2022-11-22 02:25:25,891 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 02:25:25 WrapperNode [2022-11-22 02:25:25,891 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-11-22 02:25:25,892 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-11-22 02:25:25,893 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-11-22 02:25:25,893 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-11-22 02:25:25,900 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 02:25:25" (1/1) ... [2022-11-22 02:25:25,915 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 02:25:25" (1/1) ... [2022-11-22 02:25:25,945 INFO L138 Inliner]: procedures = 142, calls = 63, calls flagged for inlining = 14, calls inlined = 13, statements flattened = 162 [2022-11-22 02:25:25,946 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-11-22 02:25:25,947 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-11-22 02:25:25,947 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-11-22 02:25:25,947 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-11-22 02:25:25,957 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 02:25:25" (1/1) ... [2022-11-22 02:25:25,958 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 02:25:25" (1/1) ... [2022-11-22 02:25:25,962 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 02:25:25" (1/1) ... [2022-11-22 02:25:25,963 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 02:25:25" (1/1) ... [2022-11-22 02:25:26,010 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 02:25:25" (1/1) ... [2022-11-22 02:25:26,030 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 02:25:25" (1/1) ... [2022-11-22 02:25:26,032 INFO L185 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 02:25:25" (1/1) ... [2022-11-22 02:25:26,034 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 02:25:25" (1/1) ... [2022-11-22 02:25:26,038 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-11-22 02:25:26,050 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-11-22 02:25:26,051 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-11-22 02:25:26,051 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-11-22 02:25:26,052 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 02:25:25" (1/1) ... [2022-11-22 02:25:26,059 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-11-22 02:25:26,084 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 [2022-11-22 02:25:26,096 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-11-22 02:25:26,103 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-11-22 02:25:26,136 INFO L130 BoogieDeclarations]: Found specification of procedure __ldv_list_add [2022-11-22 02:25:26,136 INFO L138 BoogieDeclarations]: Found implementation of procedure __ldv_list_add [2022-11-22 02:25:26,136 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_list_add [2022-11-22 02:25:26,136 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_list_add [2022-11-22 02:25:26,137 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2022-11-22 02:25:26,137 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-11-22 02:25:26,137 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2022-11-22 02:25:26,137 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_is_in_set [2022-11-22 02:25:26,137 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_is_in_set [2022-11-22 02:25:26,138 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2022-11-22 02:25:26,138 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-11-22 02:25:26,138 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2022-11-22 02:25:26,138 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_list_del [2022-11-22 02:25:26,138 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_list_del [2022-11-22 02:25:26,139 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-11-22 02:25:26,139 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_successful_malloc [2022-11-22 02:25:26,139 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_successful_malloc [2022-11-22 02:25:26,140 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-11-22 02:25:26,140 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-11-22 02:25:26,312 INFO L235 CfgBuilder]: Building ICFG [2022-11-22 02:25:26,315 INFO L261 CfgBuilder]: Building CFG for each procedure with an implementation [2022-11-22 02:25:26,713 INFO L276 CfgBuilder]: Performing block encoding [2022-11-22 02:25:26,807 INFO L295 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-11-22 02:25:26,808 INFO L300 CfgBuilder]: Removed 5 assume(true) statements. [2022-11-22 02:25:26,810 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.11 02:25:26 BoogieIcfgContainer [2022-11-22 02:25:26,811 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-11-22 02:25:26,814 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-11-22 02:25:26,814 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-11-22 02:25:26,818 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-11-22 02:25:26,818 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 22.11 02:25:25" (1/3) ... [2022-11-22 02:25:26,819 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5a2c16ee and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.11 02:25:26, skipping insertion in model container [2022-11-22 02:25:26,819 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 02:25:25" (2/3) ... [2022-11-22 02:25:26,820 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5a2c16ee and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.11 02:25:26, skipping insertion in model container [2022-11-22 02:25:26,820 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.11 02:25:26" (3/3) ... [2022-11-22 02:25:26,821 INFO L112 eAbstractionObserver]: Analyzing ICFG test_mutex_unbounded-2.i [2022-11-22 02:25:26,843 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-11-22 02:25:26,843 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 3 error locations. [2022-11-22 02:25:26,895 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-11-22 02:25:26,903 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=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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;@4af64904, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2022-11-22 02:25:26,903 INFO L358 AbstractCegarLoop]: Starting to check reachability of 3 error locations. [2022-11-22 02:25:26,908 INFO L276 IsEmpty]: Start isEmpty. Operand has 54 states, 35 states have (on average 1.4) internal successors, (49), 39 states have internal predecessors, (49), 10 states have call successors, (10), 5 states have call predecessors, (10), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-11-22 02:25:26,917 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2022-11-22 02:25:26,917 INFO L187 NwaCegarLoop]: Found error trace [2022-11-22 02:25:26,918 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2022-11-22 02:25:26,919 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-22 02:25:26,924 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-22 02:25:26,925 INFO L85 PathProgramCache]: Analyzing trace with hash -1775127545, now seen corresponding path program 1 times [2022-11-22 02:25:26,936 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-22 02:25:26,936 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [359402020] [2022-11-22 02:25:26,937 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-22 02:25:26,937 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-22 02:25:27,069 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-22 02:25:27,462 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-11-22 02:25:27,462 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-22 02:25:27,463 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [359402020] [2022-11-22 02:25:27,463 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [359402020] provided 1 perfect and 0 imperfect interpolant sequences [2022-11-22 02:25:27,463 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-11-22 02:25:27,464 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-11-22 02:25:27,465 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1392593414] [2022-11-22 02:25:27,466 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-11-22 02:25:27,470 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-11-22 02:25:27,471 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-22 02:25:27,499 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-11-22 02:25:27,500 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-11-22 02:25:27,502 INFO L87 Difference]: Start difference. First operand has 54 states, 35 states have (on average 1.4) internal successors, (49), 39 states have internal predecessors, (49), 10 states have call successors, (10), 5 states have call predecessors, (10), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-11-22 02:25:27,713 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-22 02:25:27,713 INFO L93 Difference]: Finished difference Result 145 states and 189 transitions. [2022-11-22 02:25:27,715 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-11-22 02:25:27,716 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2022-11-22 02:25:27,717 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-22 02:25:27,725 INFO L225 Difference]: With dead ends: 145 [2022-11-22 02:25:27,726 INFO L226 Difference]: Without dead ends: 92 [2022-11-22 02:25:27,729 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2022-11-22 02:25:27,732 INFO L413 NwaCegarLoop]: 53 mSDtfsCounter, 48 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 70 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 70 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 70 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-11-22 02:25:27,734 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 149 Invalid, 70 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 70 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-11-22 02:25:27,752 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2022-11-22 02:25:27,778 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 72. [2022-11-22 02:25:27,780 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 50 states have (on average 1.36) internal successors, (68), 54 states have internal predecessors, (68), 13 states have call successors, (13), 6 states have call predecessors, (13), 6 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-11-22 02:25:27,782 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 94 transitions. [2022-11-22 02:25:27,783 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 94 transitions. Word has length 6 [2022-11-22 02:25:27,784 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-22 02:25:27,784 INFO L495 AbstractCegarLoop]: Abstraction has 72 states and 94 transitions. [2022-11-22 02:25:27,784 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-11-22 02:25:27,785 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 94 transitions. [2022-11-22 02:25:27,786 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-11-22 02:25:27,786 INFO L187 NwaCegarLoop]: Found error trace [2022-11-22 02:25:27,786 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-11-22 02:25:27,787 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-11-22 02:25:27,787 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-22 02:25:27,788 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-22 02:25:27,788 INFO L85 PathProgramCache]: Analyzing trace with hash -2012936512, now seen corresponding path program 1 times [2022-11-22 02:25:27,788 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-22 02:25:27,788 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1637688289] [2022-11-22 02:25:27,789 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-22 02:25:27,789 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-22 02:25:27,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-22 02:25:27,877 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-11-22 02:25:27,877 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-22 02:25:27,878 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1637688289] [2022-11-22 02:25:27,878 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1637688289] provided 1 perfect and 0 imperfect interpolant sequences [2022-11-22 02:25:27,879 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-11-22 02:25:27,880 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-11-22 02:25:27,881 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [728670885] [2022-11-22 02:25:27,881 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-11-22 02:25:27,886 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-11-22 02:25:27,886 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-22 02:25:27,886 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-11-22 02:25:27,887 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-11-22 02:25:27,887 INFO L87 Difference]: Start difference. First operand 72 states and 94 transitions. Second operand has 4 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-11-22 02:25:28,020 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-22 02:25:28,022 INFO L93 Difference]: Finished difference Result 82 states and 109 transitions. [2022-11-22 02:25:28,023 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-11-22 02:25:28,024 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2022-11-22 02:25:28,028 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-22 02:25:28,030 INFO L225 Difference]: With dead ends: 82 [2022-11-22 02:25:28,030 INFO L226 Difference]: Without dead ends: 80 [2022-11-22 02:25:28,031 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-11-22 02:25:28,033 INFO L413 NwaCegarLoop]: 50 mSDtfsCounter, 0 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-11-22 02:25:28,033 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 144 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-11-22 02:25:28,037 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2022-11-22 02:25:28,049 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 80. [2022-11-22 02:25:28,052 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 56 states have (on average 1.3214285714285714) internal successors, (74), 60 states have internal predecessors, (74), 13 states have call successors, (13), 6 states have call predecessors, (13), 8 states have return successors, (19), 14 states have call predecessors, (19), 13 states have call successors, (19) [2022-11-22 02:25:28,059 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 106 transitions. [2022-11-22 02:25:28,060 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 106 transitions. Word has length 11 [2022-11-22 02:25:28,060 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-22 02:25:28,060 INFO L495 AbstractCegarLoop]: Abstraction has 80 states and 106 transitions. [2022-11-22 02:25:28,060 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-11-22 02:25:28,061 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 106 transitions. [2022-11-22 02:25:28,062 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-11-22 02:25:28,062 INFO L187 NwaCegarLoop]: Found error trace [2022-11-22 02:25:28,063 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-11-22 02:25:28,063 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-11-22 02:25:28,063 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-22 02:25:28,065 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-22 02:25:28,065 INFO L85 PathProgramCache]: Analyzing trace with hash 1855141470, now seen corresponding path program 1 times [2022-11-22 02:25:28,066 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-22 02:25:28,066 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2087609063] [2022-11-22 02:25:28,066 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-22 02:25:28,066 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-22 02:25:28,087 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-22 02:25:28,251 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-11-22 02:25:28,252 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-22 02:25:28,252 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2087609063] [2022-11-22 02:25:28,252 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2087609063] provided 1 perfect and 0 imperfect interpolant sequences [2022-11-22 02:25:28,252 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-11-22 02:25:28,252 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-11-22 02:25:28,252 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1281482369] [2022-11-22 02:25:28,253 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-11-22 02:25:28,253 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-11-22 02:25:28,253 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-22 02:25:28,253 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-11-22 02:25:28,254 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-11-22 02:25:28,254 INFO L87 Difference]: Start difference. First operand 80 states and 106 transitions. Second operand has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-11-22 02:25:28,444 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-22 02:25:28,444 INFO L93 Difference]: Finished difference Result 139 states and 178 transitions. [2022-11-22 02:25:28,445 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-11-22 02:25:28,445 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-11-22 02:25:28,446 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-22 02:25:28,447 INFO L225 Difference]: With dead ends: 139 [2022-11-22 02:25:28,447 INFO L226 Difference]: Without dead ends: 65 [2022-11-22 02:25:28,448 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2022-11-22 02:25:28,449 INFO L413 NwaCegarLoop]: 54 mSDtfsCounter, 12 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 61 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-11-22 02:25:28,449 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 138 Invalid, 61 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-11-22 02:25:28,450 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2022-11-22 02:25:28,468 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 60. [2022-11-22 02:25:28,468 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 39 states have (on average 1.2564102564102564) internal successors, (49), 43 states have internal predecessors, (49), 11 states have call successors, (11), 6 states have call predecessors, (11), 7 states have return successors, (14), 11 states have call predecessors, (14), 11 states have call successors, (14) [2022-11-22 02:25:28,469 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 74 transitions. [2022-11-22 02:25:28,469 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 74 transitions. Word has length 12 [2022-11-22 02:25:28,469 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-22 02:25:28,470 INFO L495 AbstractCegarLoop]: Abstraction has 60 states and 74 transitions. [2022-11-22 02:25:28,470 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-11-22 02:25:28,470 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 74 transitions. [2022-11-22 02:25:28,472 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2022-11-22 02:25:28,473 INFO L187 NwaCegarLoop]: Found error trace [2022-11-22 02:25:28,473 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-11-22 02:25:28,473 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-11-22 02:25:28,474 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-22 02:25:28,477 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-22 02:25:28,477 INFO L85 PathProgramCache]: Analyzing trace with hash -598092077, now seen corresponding path program 1 times [2022-11-22 02:25:28,478 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-22 02:25:28,478 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [839117194] [2022-11-22 02:25:28,478 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-22 02:25:28,478 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-22 02:25:28,533 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-22 02:25:28,990 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-11-22 02:25:28,990 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-22 02:25:28,991 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [839117194] [2022-11-22 02:25:28,991 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [839117194] provided 0 perfect and 1 imperfect interpolant sequences [2022-11-22 02:25:28,992 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [404613503] [2022-11-22 02:25:28,992 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-22 02:25:28,992 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-22 02:25:28,992 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 [2022-11-22 02:25:28,998 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-11-22 02:25:29,019 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-11-22 02:25:29,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-22 02:25:29,161 INFO L263 TraceCheckSpWp]: Trace formula consists of 278 conjuncts, 50 conjunts are in the unsatisfiable core [2022-11-22 02:25:29,171 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-11-22 02:25:29,367 INFO L321 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2022-11-22 02:25:29,368 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2022-11-22 02:25:29,680 INFO L321 Elim1Store]: treesize reduction 117, result has 35.4 percent of original size [2022-11-22 02:25:29,681 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 92 treesize of output 229 [2022-11-22 02:25:29,701 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 8 treesize of output 7 [2022-11-22 02:25:29,722 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 8 treesize of output 7 [2022-11-22 02:25:29,742 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 8 treesize of output 7 [2022-11-22 02:25:30,204 INFO L321 Elim1Store]: treesize reduction 20, result has 4.8 percent of original size [2022-11-22 02:25:30,205 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 62 treesize of output 21 [2022-11-22 02:25:30,228 INFO L350 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 5 treesize of output 3 [2022-11-22 02:25:30,280 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:30,286 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 64 treesize of output 30 [2022-11-22 02:25:30,294 INFO L350 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 5 treesize of output 3 [2022-11-22 02:25:30,299 INFO L350 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 5 treesize of output 3 [2022-11-22 02:25:30,792 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 8 [2022-11-22 02:25:30,820 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-11-22 02:25:30,820 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-11-22 02:25:31,199 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-11-22 02:25:31,199 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 746 treesize of output 735 [2022-11-22 02:25:31,216 INFO L350 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 902 treesize of output 870 [2022-11-22 02:25:31,234 INFO L350 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 958 treesize of output 942 [2022-11-22 02:25:31,257 INFO L350 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 942 treesize of output 938 [2022-11-22 02:25:31,277 INFO L350 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 938 treesize of output 930 [2022-11-22 02:25:31,441 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:31,541 INFO L173 IndexEqualityManager]: detected equality via solver [2022-11-22 02:25:31,542 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:31,545 INFO L350 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 30 treesize of output 28 [2022-11-22 02:25:31,548 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:31,554 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:31,707 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-11-22 02:25:31,708 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [404613503] provided 0 perfect and 2 imperfect interpolant sequences [2022-11-22 02:25:31,708 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1029280183] [2022-11-22 02:25:31,730 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2022-11-22 02:25:31,731 INFO L166 IcfgInterpreter]: Building call graph [2022-11-22 02:25:31,740 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2022-11-22 02:25:31,746 INFO L176 IcfgInterpreter]: Starting interpretation [2022-11-22 02:25:31,747 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2022-11-22 02:25:31,854 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2022-11-22 02:25:31,864 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 9 [2022-11-22 02:25:32,067 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:32,172 INFO L321 Elim1Store]: treesize reduction 128, result has 32.3 percent of original size [2022-11-22 02:25:32,172 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 68 [2022-11-22 02:25:32,231 INFO L321 Elim1Store]: treesize reduction 25, result has 43.2 percent of original size [2022-11-22 02:25:32,232 INFO L350 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 1 case distinctions, treesize of input 35 treesize of output 19 [2022-11-22 02:25:32,268 INFO L321 Elim1Store]: treesize reduction 25, result has 40.5 percent of original size [2022-11-22 02:25:32,268 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 39 treesize of output 31 [2022-11-22 02:25:32,302 INFO L321 Elim1Store]: treesize reduction 25, result has 43.2 percent of original size [2022-11-22 02:25:32,303 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 33 treesize of output 31 [2022-11-22 02:25:32,318 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:32,402 INFO L321 Elim1Store]: treesize reduction 147, result has 22.2 percent of original size [2022-11-22 02:25:32,403 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 49 [2022-11-22 02:25:32,431 INFO L350 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 7 treesize of output 3 [2022-11-22 02:25:32,435 INFO L350 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 7 treesize of output 3 [2022-11-22 02:25:32,447 INFO L350 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 7 treesize of output 3 [2022-11-22 02:25:32,451 INFO L350 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 7 treesize of output 3 [2022-11-22 02:25:32,478 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:32,479 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:32,480 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:25:32,493 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:32,494 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:32,495 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:25:32,537 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:32,538 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:32,539 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:25:32,551 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:32,552 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:32,553 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:25:32,623 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:32,632 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:32,665 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:32,672 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:32,880 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:32,881 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:32,882 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:25:32,893 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:32,894 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:32,895 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:25:33,088 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:33,089 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:33,091 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:25:33,104 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:33,105 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:33,106 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:25:33,390 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:33,399 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:33,415 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:33,425 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:33,610 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:33,620 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:33,630 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:33,639 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:34,449 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_successful_malloc with input of size 27 for LOIs [2022-11-22 02:25:34,456 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_list_add with input of size 34 for LOIs [2022-11-22 02:25:34,508 INFO L197 IcfgInterpreter]: Interpreting procedure __ldv_list_add with input of size 42 for LOIs [2022-11-22 02:25:34,551 INFO L180 IcfgInterpreter]: Interpretation finished [2022-11-22 02:25:38,613 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1013#(and (<= 0 (+ |ULTIMATE.start_foo_~N~0#1| 2147483648)) (= |ULTIMATE.start_ldv_set_empty_#in~s#1.offset| |~#mutexes~0.offset|) (= |ULTIMATE.start_foo_~__mptr~5#1.base| (select (select |#memory_$Pointer$.base| |~#drvlist~0.base|) |~#drvlist~0.offset|)) (= |ULTIMATE.start_foo_~__mptr~7#1.offset| (select (select |#memory_$Pointer$.offset| |~#drvlist~0.base|) |~#drvlist~0.offset|)) (= |ULTIMATE.start_ldv_list_empty_~head#1.base| |ULTIMATE.start_ldv_list_empty_#in~head#1.base|) (= |ULTIMATE.start_ldv_list_empty_#res#1| |ULTIMATE.start_ldv_set_empty_#res#1|) (<= |ULTIMATE.start_foo_~N~0#1| |ULTIMATE.start_foo_~i~0#1|) (= (select (select |#memory_$Pointer$.base| |~#drvlist~0.base|) |~#drvlist~0.offset|) |ULTIMATE.start_foo_~__mptr~7#1.base|) (= (ite (and (= (select (select |#memory_$Pointer$.offset| |ULTIMATE.start_ldv_list_empty_~head#1.base|) |ULTIMATE.start_ldv_list_empty_~head#1.offset|) |ULTIMATE.start_ldv_list_empty_~head#1.offset|) (= |ULTIMATE.start_ldv_list_empty_~head#1.base| (select (select |#memory_$Pointer$.base| |ULTIMATE.start_ldv_list_empty_~head#1.base|) |ULTIMATE.start_ldv_list_empty_~head#1.offset|))) 1 0) |ULTIMATE.start_ldv_list_empty_#res#1|) (<= |#NULL.offset| 0) (<= 4 |~#drvlist~0.base|) (= |ULTIMATE.start_ldv_set_empty_#res#1| 0) (= |~#mutexes~0.base| |ULTIMATE.start_ldv_set_empty_#in~s#1.base|) (= |ULTIMATE.start_ldv_set_empty_#in~s#1.offset| |ULTIMATE.start_ldv_set_empty_~s#1.offset|) (= |ULTIMATE.start_foo_~__mptr~5#1.offset| |~#drvlist~0.offset|) (<= 3 |~#mutexes~0.base|) (= |ULTIMATE.start_ldv_set_empty_~s#1.base| |ULTIMATE.start_ldv_list_empty_#in~head#1.base|) (= |ULTIMATE.start_foo_~__mptr~7#1.offset| (+ 8 |ULTIMATE.start_foo_~me~1#1.offset|)) (= |ULTIMATE.start_ldv_list_empty_#in~head#1.offset| |ULTIMATE.start_ldv_list_empty_~head#1.offset|) (<= |~#drvlist~0.base| 4) (= |ULTIMATE.start_ldv_set_empty_~s#1.offset| |ULTIMATE.start_ldv_list_empty_#in~head#1.offset|) (= |~#drvlist~0.base| |ULTIMATE.start_foo_~me~1#1.base|) (= |ULTIMATE.start_foo_~__mptr~5#1.base| |~#drvlist~0.base|) (= |ULTIMATE.start_ldv_set_empty_~s#1.base| |ULTIMATE.start_ldv_set_empty_#in~s#1.base|) (<= 0 |#NULL.offset|) (<= |ULTIMATE.start_foo_~N~0#1| 2147483647) (<= |~#mutexes~0.base| 3) (or (and (= |~#drvlist~0.offset| 0) (= |~#mutexes~0.offset| 0) (= |ULTIMATE.start_foo_~i~0#1| 0) (= |#NULL.base| 0)) (and (= |~#drvlist~0.offset| 0) (= |ULTIMATE.start_foo_~me~0#1.offset| 0) (= |~#mutexes~0.offset| 0) (= |#NULL.base| 0))) (<= 0 |#StackHeapBarrier|) (= |ULTIMATE.start_foo_~__mptr~5#1.offset| (select (select |#memory_$Pointer$.offset| |~#drvlist~0.base|) |~#drvlist~0.offset|)) (<= 0 |ULTIMATE.start_foo_~i~0#1|))' at error location [2022-11-22 02:25:38,613 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2022-11-22 02:25:38,614 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-11-22 02:25:38,614 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12, 12] total 32 [2022-11-22 02:25:38,614 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [207478910] [2022-11-22 02:25:38,614 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-11-22 02:25:38,615 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2022-11-22 02:25:38,615 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-22 02:25:38,616 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2022-11-22 02:25:38,617 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=198, Invalid=2056, Unknown=2, NotChecked=0, Total=2256 [2022-11-22 02:25:38,617 INFO L87 Difference]: Start difference. First operand 60 states and 74 transitions. Second operand has 32 states, 20 states have (on average 1.65) internal successors, (33), 25 states have internal predecessors, (33), 9 states have call successors, (9), 4 states have call predecessors, (9), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-11-22 02:25:40,542 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-22 02:25:40,542 INFO L93 Difference]: Finished difference Result 143 states and 176 transitions. [2022-11-22 02:25:40,543 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2022-11-22 02:25:40,543 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 20 states have (on average 1.65) internal successors, (33), 25 states have internal predecessors, (33), 9 states have call successors, (9), 4 states have call predecessors, (9), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Word has length 19 [2022-11-22 02:25:40,544 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-22 02:25:40,550 INFO L225 Difference]: With dead ends: 143 [2022-11-22 02:25:40,550 INFO L226 Difference]: Without dead ends: 119 [2022-11-22 02:25:40,552 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 21 SyntacticMatches, 1 SemanticMatches, 62 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 771 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=427, Invalid=3603, Unknown=2, NotChecked=0, Total=4032 [2022-11-22 02:25:40,555 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 503 mSDsluCounter, 416 mSDsCounter, 0 mSdLazyCounter, 1148 mSolverCounterSat, 253 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 503 SdHoareTripleChecker+Valid, 449 SdHoareTripleChecker+Invalid, 1401 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 253 IncrementalHoareTripleChecker+Valid, 1148 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2022-11-22 02:25:40,557 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [503 Valid, 449 Invalid, 1401 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [253 Valid, 1148 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2022-11-22 02:25:40,558 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2022-11-22 02:25:40,587 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 96. [2022-11-22 02:25:40,588 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 65 states have (on average 1.3076923076923077) internal successors, (85), 71 states have internal predecessors, (85), 16 states have call successors, (16), 10 states have call predecessors, (16), 12 states have return successors, (21), 15 states have call predecessors, (21), 16 states have call successors, (21) [2022-11-22 02:25:40,589 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 122 transitions. [2022-11-22 02:25:40,589 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 122 transitions. Word has length 19 [2022-11-22 02:25:40,589 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-22 02:25:40,590 INFO L495 AbstractCegarLoop]: Abstraction has 96 states and 122 transitions. [2022-11-22 02:25:40,590 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 20 states have (on average 1.65) internal successors, (33), 25 states have internal predecessors, (33), 9 states have call successors, (9), 4 states have call predecessors, (9), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-11-22 02:25:40,590 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 122 transitions. [2022-11-22 02:25:40,591 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2022-11-22 02:25:40,591 INFO L187 NwaCegarLoop]: Found error trace [2022-11-22 02:25:40,591 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-11-22 02:25:40,603 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-11-22 02:25:40,792 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-22 02:25:40,792 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-22 02:25:40,793 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-22 02:25:40,793 INFO L85 PathProgramCache]: Analyzing trace with hash 839979050, now seen corresponding path program 1 times [2022-11-22 02:25:40,793 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-22 02:25:40,793 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [735015393] [2022-11-22 02:25:40,793 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-22 02:25:40,793 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-22 02:25:40,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-22 02:25:43,772 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-11-22 02:25:43,773 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-22 02:25:43,773 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [735015393] [2022-11-22 02:25:43,773 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [735015393] provided 0 perfect and 1 imperfect interpolant sequences [2022-11-22 02:25:43,773 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1885772935] [2022-11-22 02:25:43,773 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-22 02:25:43,774 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-22 02:25:43,774 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 [2022-11-22 02:25:43,779 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-11-22 02:25:43,788 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-11-22 02:25:43,928 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-22 02:25:43,932 INFO L263 TraceCheckSpWp]: Trace formula consists of 286 conjuncts, 107 conjunts are in the unsatisfiable core [2022-11-22 02:25:43,938 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-11-22 02:25:44,213 INFO L321 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2022-11-22 02:25:44,213 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2022-11-22 02:25:44,366 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2022-11-22 02:25:44,378 INFO L350 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 7 treesize of output 3 [2022-11-22 02:25:44,803 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 33 [2022-11-22 02:25:44,843 INFO L321 Elim1Store]: treesize reduction 50, result has 29.6 percent of original size [2022-11-22 02:25:44,844 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 55 treesize of output 57 [2022-11-22 02:25:44,873 INFO L321 Elim1Store]: treesize reduction 24, result has 38.5 percent of original size [2022-11-22 02:25:44,874 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 61 treesize of output 64 [2022-11-22 02:25:44,889 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-11-22 02:25:44,890 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 50 treesize of output 42 [2022-11-22 02:25:44,913 INFO L321 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2022-11-22 02:25:44,913 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 32 [2022-11-22 02:25:44,920 INFO L350 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 7 treesize of output 3 [2022-11-22 02:25:45,240 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-11-22 02:25:45,240 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-11-22 02:25:47,835 WARN L837 $PredicateComparison]: unable to prove that (let ((.cse0 (select (select |c_#memory_$Pointer$.base| |c_~#drvlist~0.base|) |c_~#drvlist~0.offset|))) (and (forall ((v___ldv_list_add_~next.offset_16 Int) (v_ArrVal_258 (Array Int Int)) (v_ArrVal_257 (Array Int Int))) (= |c_~#mutexes~0.base| (select (select (store (store (store |c_#memory_$Pointer$.base| .cse0 (store (select |c_#memory_$Pointer$.base| .cse0) (+ v___ldv_list_add_~next.offset_16 4) |c_ULTIMATE.start_foo_~me~0#1.base|)) |c_ULTIMATE.start_foo_~me~0#1.base| v_ArrVal_257) |c_~#drvlist~0.base| v_ArrVal_258) |c_~#mutexes~0.base|) |c_~#mutexes~0.offset|))) (forall ((v___ldv_list_add_~next.offset_16 Int) (v_ArrVal_256 (Array Int Int)) (v_ArrVal_255 (Array Int Int))) (= (select (select (store (store (store |c_#memory_$Pointer$.offset| .cse0 (store (select |c_#memory_$Pointer$.offset| .cse0) (+ v___ldv_list_add_~next.offset_16 4) (+ |c_ULTIMATE.start_foo_~me~0#1.offset| 8))) |c_ULTIMATE.start_foo_~me~0#1.base| v_ArrVal_255) |c_~#drvlist~0.base| v_ArrVal_256) |c_~#mutexes~0.base|) |c_~#mutexes~0.offset|) |c_~#mutexes~0.offset|)))) is different from false [2022-11-22 02:25:47,841 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1885772935] provided 0 perfect and 1 imperfect interpolant sequences [2022-11-22 02:25:47,841 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [750731160] [2022-11-22 02:25:47,844 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2022-11-22 02:25:47,844 INFO L166 IcfgInterpreter]: Building call graph [2022-11-22 02:25:47,845 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2022-11-22 02:25:47,845 INFO L176 IcfgInterpreter]: Starting interpretation [2022-11-22 02:25:47,845 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2022-11-22 02:25:47,887 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 9 [2022-11-22 02:25:47,895 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2022-11-22 02:25:48,132 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:48,235 INFO L321 Elim1Store]: treesize reduction 147, result has 22.2 percent of original size [2022-11-22 02:25:48,236 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 49 [2022-11-22 02:25:48,290 INFO L321 Elim1Store]: treesize reduction 25, result has 43.2 percent of original size [2022-11-22 02:25:48,290 INFO L350 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 1 case distinctions, treesize of input 35 treesize of output 19 [2022-11-22 02:25:48,328 INFO L321 Elim1Store]: treesize reduction 25, result has 40.5 percent of original size [2022-11-22 02:25:48,329 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 39 treesize of output 31 [2022-11-22 02:25:48,371 INFO L321 Elim1Store]: treesize reduction 25, result has 43.2 percent of original size [2022-11-22 02:25:48,372 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 33 treesize of output 31 [2022-11-22 02:25:48,387 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:48,510 INFO L321 Elim1Store]: treesize reduction 128, result has 32.3 percent of original size [2022-11-22 02:25:48,511 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 68 [2022-11-22 02:25:48,533 INFO L350 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 7 treesize of output 3 [2022-11-22 02:25:48,545 INFO L350 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 7 treesize of output 3 [2022-11-22 02:25:48,557 INFO L350 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 7 treesize of output 3 [2022-11-22 02:25:48,562 INFO L350 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 7 treesize of output 3 [2022-11-22 02:25:48,621 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:48,622 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:48,623 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:25:48,650 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:48,652 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:48,653 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:25:48,669 WARN L207 Elim1Store]: Array PQE input equivalent to false [2022-11-22 02:25:48,857 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:48,858 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:48,860 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:25:48,870 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:48,872 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:25:48,873 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:25:48,890 WARN L207 Elim1Store]: Array PQE input equivalent to false [2022-11-22 02:25:49,037 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:49,045 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:49,057 WARN L207 Elim1Store]: Array PQE input equivalent to false [2022-11-22 02:25:49,059 WARN L207 Elim1Store]: Array PQE input equivalent to false [2022-11-22 02:25:49,168 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:49,176 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:25:49,188 WARN L207 Elim1Store]: Array PQE input equivalent to false [2022-11-22 02:25:49,190 WARN L207 Elim1Store]: Array PQE input equivalent to false [2022-11-22 02:25:50,591 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_successful_malloc with input of size 27 for LOIs [2022-11-22 02:25:50,597 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_is_in_set with input of size 90 for LOIs [2022-11-22 02:25:50,670 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_list_add with input of size 34 for LOIs [2022-11-22 02:25:50,723 INFO L197 IcfgInterpreter]: Interpreting procedure __ldv_list_add with input of size 42 for LOIs [2022-11-22 02:25:50,774 INFO L180 IcfgInterpreter]: Interpretation finished [2022-11-22 02:25:55,697 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1533#(and (= |~#drvlist~0.offset| 0) (= |~#mutexes~0.base| 3) (= |ULTIMATE.start_foo_~me~0#1.offset| 0) (= |~#mutexes~0.offset| 0) (= |#NULL.offset| 0) (<= |ULTIMATE.start_foo_~N~0#1| 2147483647) (<= 1 |ULTIMATE.start_foo_~i~0#1|) (<= 0 |#StackHeapBarrier|) (= 4 |~#drvlist~0.base|) (<= 0 |ULTIMATE.start_foo_~N~0#1|) (= |#NULL.base| 0))' at error location [2022-11-22 02:25:55,698 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2022-11-22 02:25:55,698 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-11-22 02:25:55,698 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13] total 27 [2022-11-22 02:25:55,698 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [923795414] [2022-11-22 02:25:55,698 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-11-22 02:25:55,699 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2022-11-22 02:25:55,699 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-22 02:25:55,699 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2022-11-22 02:25:55,700 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=213, Invalid=2236, Unknown=5, NotChecked=96, Total=2550 [2022-11-22 02:25:55,700 INFO L87 Difference]: Start difference. First operand 96 states and 122 transitions. Second operand has 27 states, 18 states have (on average 1.7222222222222223) internal successors, (31), 20 states have internal predecessors, (31), 8 states have call successors, (8), 6 states have call predecessors, (8), 8 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2022-11-22 02:25:59,623 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-22 02:25:59,623 INFO L93 Difference]: Finished difference Result 242 states and 315 transitions. [2022-11-22 02:25:59,624 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2022-11-22 02:25:59,624 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 18 states have (on average 1.7222222222222223) internal successors, (31), 20 states have internal predecessors, (31), 8 states have call successors, (8), 6 states have call predecessors, (8), 8 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) Word has length 25 [2022-11-22 02:25:59,624 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-22 02:25:59,626 INFO L225 Difference]: With dead ends: 242 [2022-11-22 02:25:59,626 INFO L226 Difference]: Without dead ends: 158 [2022-11-22 02:25:59,628 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 71 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 1449 ImplicationChecksByTransitivity, 10.3s TimeCoverageRelationStatistics Valid=492, Invalid=4617, Unknown=7, NotChecked=140, Total=5256 [2022-11-22 02:25:59,629 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 163 mSDsluCounter, 310 mSDsCounter, 0 mSdLazyCounter, 856 mSolverCounterSat, 101 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 163 SdHoareTripleChecker+Valid, 347 SdHoareTripleChecker+Invalid, 961 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 101 IncrementalHoareTripleChecker+Valid, 856 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2022-11-22 02:25:59,629 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [163 Valid, 347 Invalid, 961 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [101 Valid, 856 Invalid, 4 Unknown, 0 Unchecked, 1.9s Time] [2022-11-22 02:25:59,630 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 158 states. [2022-11-22 02:25:59,653 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 158 to 120. [2022-11-22 02:25:59,654 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 81 states have (on average 1.2962962962962963) internal successors, (105), 88 states have internal predecessors, (105), 20 states have call successors, (20), 13 states have call predecessors, (20), 16 states have return successors, (26), 19 states have call predecessors, (26), 20 states have call successors, (26) [2022-11-22 02:25:59,655 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 151 transitions. [2022-11-22 02:25:59,655 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 151 transitions. Word has length 25 [2022-11-22 02:25:59,656 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-22 02:25:59,656 INFO L495 AbstractCegarLoop]: Abstraction has 120 states and 151 transitions. [2022-11-22 02:25:59,656 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 18 states have (on average 1.7222222222222223) internal successors, (31), 20 states have internal predecessors, (31), 8 states have call successors, (8), 6 states have call predecessors, (8), 8 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2022-11-22 02:25:59,656 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 151 transitions. [2022-11-22 02:25:59,657 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-11-22 02:25:59,657 INFO L187 NwaCegarLoop]: Found error trace [2022-11-22 02:25:59,658 INFO L195 NwaCegarLoop]: trace histogram [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] [2022-11-22 02:25:59,676 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-11-22 02:25:59,873 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-22 02:25:59,873 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-22 02:25:59,873 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-22 02:25:59,874 INFO L85 PathProgramCache]: Analyzing trace with hash -1101495842, now seen corresponding path program 2 times [2022-11-22 02:25:59,874 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-22 02:25:59,874 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1132076057] [2022-11-22 02:25:59,874 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-22 02:25:59,874 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-22 02:25:59,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-22 02:26:05,972 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-11-22 02:26:05,972 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-22 02:26:05,973 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1132076057] [2022-11-22 02:26:05,973 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1132076057] provided 0 perfect and 1 imperfect interpolant sequences [2022-11-22 02:26:05,973 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [785884699] [2022-11-22 02:26:05,973 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-11-22 02:26:05,973 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-22 02:26:05,974 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 [2022-11-22 02:26:05,975 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-11-22 02:26:05,990 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-11-22 02:26:06,183 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-11-22 02:26:06,183 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-11-22 02:26:06,189 INFO L263 TraceCheckSpWp]: Trace formula consists of 453 conjuncts, 200 conjunts are in the unsatisfiable core [2022-11-22 02:26:06,198 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-11-22 02:26:06,568 INFO L321 Elim1Store]: treesize reduction 18, result has 35.7 percent of original size [2022-11-22 02:26:06,569 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 17 treesize of output 21 [2022-11-22 02:26:06,816 INFO L350 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 7 treesize of output 3 [2022-11-22 02:26:06,831 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2022-11-22 02:26:07,627 INFO L321 Elim1Store]: treesize reduction 50, result has 29.6 percent of original size [2022-11-22 02:26:07,628 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 95 treesize of output 75 [2022-11-22 02:26:07,705 INFO L321 Elim1Store]: treesize reduction 67, result has 26.4 percent of original size [2022-11-22 02:26:07,706 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 5 new quantified variables, introduced 4 case distinctions, treesize of input 128 treesize of output 165 [2022-11-22 02:26:07,720 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 33 [2022-11-22 02:26:07,770 INFO L321 Elim1Store]: treesize reduction 22, result has 47.6 percent of original size [2022-11-22 02:26:07,770 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 154 treesize of output 114 [2022-11-22 02:26:07,809 INFO L321 Elim1Store]: treesize reduction 19, result has 47.2 percent of original size [2022-11-22 02:26:07,810 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 40 [2022-11-22 02:26:07,824 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2022-11-22 02:26:07,836 INFO L350 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 7 treesize of output 3 [2022-11-22 02:26:07,899 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 73 treesize of output 29 [2022-11-22 02:26:07,907 INFO L350 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 9 treesize of output 7 [2022-11-22 02:26:08,621 INFO L321 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2022-11-22 02:26:08,622 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2022-11-22 02:26:08,858 INFO L350 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 7 treesize of output 3 [2022-11-22 02:26:08,865 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 8 [2022-11-22 02:26:09,456 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 33 [2022-11-22 02:26:09,501 INFO L321 Elim1Store]: treesize reduction 46, result has 35.2 percent of original size [2022-11-22 02:26:09,502 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 56 treesize of output 62 [2022-11-22 02:26:09,561 INFO L321 Elim1Store]: treesize reduction 47, result has 42.7 percent of original size [2022-11-22 02:26:09,562 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 65 treesize of output 88 [2022-11-22 02:26:09,620 INFO L321 Elim1Store]: treesize reduction 45, result has 43.0 percent of original size [2022-11-22 02:26:09,621 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 30 treesize of output 56 [2022-11-22 02:26:09,652 INFO L350 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 5 treesize of output 3 [2022-11-22 02:26:09,719 INFO L350 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 7 treesize of output 3 [2022-11-22 02:26:09,728 INFO L350 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 7 treesize of output 3 [2022-11-22 02:26:09,735 WARN L207 Elim1Store]: Array PQE input equivalent to false [2022-11-22 02:26:09,767 WARN L207 Elim1Store]: Array PQE input equivalent to false [2022-11-22 02:26:10,155 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-11-22 02:26:10,155 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-11-22 02:26:13,765 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [785884699] provided 0 perfect and 1 imperfect interpolant sequences [2022-11-22 02:26:13,765 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [453664083] [2022-11-22 02:26:13,768 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2022-11-22 02:26:13,768 INFO L166 IcfgInterpreter]: Building call graph [2022-11-22 02:26:13,769 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2022-11-22 02:26:13,769 INFO L176 IcfgInterpreter]: Starting interpretation [2022-11-22 02:26:13,769 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2022-11-22 02:26:13,813 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2022-11-22 02:26:13,826 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 9 [2022-11-22 02:26:14,112 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:14,279 INFO L321 Elim1Store]: treesize reduction 131, result has 34.8 percent of original size [2022-11-22 02:26:14,280 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 81 treesize of output 70 [2022-11-22 02:26:14,298 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:14,402 INFO L321 Elim1Store]: treesize reduction 147, result has 22.2 percent of original size [2022-11-22 02:26:14,402 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 49 [2022-11-22 02:26:14,416 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:14,567 INFO L321 Elim1Store]: treesize reduction 128, result has 32.3 percent of original size [2022-11-22 02:26:14,567 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 68 [2022-11-22 02:26:14,598 INFO L350 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 7 treesize of output 3 [2022-11-22 02:26:14,603 INFO L350 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 7 treesize of output 3 [2022-11-22 02:26:14,614 INFO L350 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 7 treesize of output 3 [2022-11-22 02:26:14,619 INFO L350 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 7 treesize of output 3 [2022-11-22 02:26:14,662 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:14,663 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:14,664 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:26:14,676 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:14,677 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:14,678 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:26:14,690 WARN L207 Elim1Store]: Array PQE input equivalent to false [2022-11-22 02:26:14,817 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:14,819 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:14,819 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:26:14,831 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:14,833 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:14,833 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:26:14,847 WARN L207 Elim1Store]: Array PQE input equivalent to false [2022-11-22 02:26:14,891 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:14,898 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:14,921 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:14,930 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:16,049 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_successful_malloc with input of size 27 for LOIs [2022-11-22 02:26:16,055 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_is_in_set with input of size 89 for LOIs [2022-11-22 02:26:16,116 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_list_add with input of size 34 for LOIs [2022-11-22 02:26:16,160 INFO L197 IcfgInterpreter]: Interpreting procedure __ldv_list_add with input of size 42 for LOIs [2022-11-22 02:26:16,205 INFO L180 IcfgInterpreter]: Interpretation finished [2022-11-22 02:26:23,084 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2294#(and (= |~#drvlist~0.offset| 0) (= |~#mutexes~0.base| 3) (= |ULTIMATE.start_foo_~me~0#1.offset| 0) (= |~#mutexes~0.offset| 0) (= |#NULL.offset| 0) (<= |ULTIMATE.start_foo_~N~0#1| 2147483647) (<= 1 |ULTIMATE.start_foo_~i~0#1|) (<= 0 |#StackHeapBarrier|) (= 4 |~#drvlist~0.base|) (<= 0 |ULTIMATE.start_foo_~N~0#1|) (= |#NULL.base| 0))' at error location [2022-11-22 02:26:23,084 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2022-11-22 02:26:23,084 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-11-22 02:26:23,084 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 43 [2022-11-22 02:26:23,085 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1154749094] [2022-11-22 02:26:23,085 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-11-22 02:26:23,085 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 43 states [2022-11-22 02:26:23,086 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-22 02:26:23,086 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2022-11-22 02:26:23,087 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=339, Invalid=4074, Unknown=9, NotChecked=0, Total=4422 [2022-11-22 02:26:23,088 INFO L87 Difference]: Start difference. First operand 120 states and 151 transitions. Second operand has 43 states, 27 states have (on average 1.6296296296296295) internal successors, (44), 31 states have internal predecessors, (44), 13 states have call successors, (13), 9 states have call predecessors, (13), 14 states have return successors, (14), 13 states have call predecessors, (14), 13 states have call successors, (14) [2022-11-22 02:26:29,602 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-22 02:26:29,602 INFO L93 Difference]: Finished difference Result 234 states and 298 transitions. [2022-11-22 02:26:29,603 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2022-11-22 02:26:29,603 INFO L78 Accepts]: Start accepts. Automaton has has 43 states, 27 states have (on average 1.6296296296296295) internal successors, (44), 31 states have internal predecessors, (44), 13 states have call successors, (13), 9 states have call predecessors, (13), 14 states have return successors, (14), 13 states have call predecessors, (14), 13 states have call successors, (14) Word has length 38 [2022-11-22 02:26:29,603 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-22 02:26:29,606 INFO L225 Difference]: With dead ends: 234 [2022-11-22 02:26:29,606 INFO L226 Difference]: Without dead ends: 150 [2022-11-22 02:26:29,609 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 54 SyntacticMatches, 0 SemanticMatches, 91 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3004 ImplicationChecksByTransitivity, 16.9s TimeCoverageRelationStatistics Valid=732, Invalid=7810, Unknown=14, NotChecked=0, Total=8556 [2022-11-22 02:26:29,610 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 190 mSDsluCounter, 397 mSDsCounter, 0 mSdLazyCounter, 1214 mSolverCounterSat, 134 mSolverCounterUnsat, 21 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 190 SdHoareTripleChecker+Valid, 434 SdHoareTripleChecker+Invalid, 1369 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 134 IncrementalHoareTripleChecker+Valid, 1214 IncrementalHoareTripleChecker+Invalid, 21 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.3s IncrementalHoareTripleChecker+Time [2022-11-22 02:26:29,610 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [190 Valid, 434 Invalid, 1369 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [134 Valid, 1214 Invalid, 21 Unknown, 0 Unchecked, 3.3s Time] [2022-11-22 02:26:29,611 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 150 states. [2022-11-22 02:26:29,634 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 150 to 101. [2022-11-22 02:26:29,635 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 101 states, 67 states have (on average 1.2985074626865671) internal successors, (87), 74 states have internal predecessors, (87), 17 states have call successors, (17), 12 states have call predecessors, (17), 14 states have return successors, (21), 15 states have call predecessors, (21), 17 states have call successors, (21) [2022-11-22 02:26:29,636 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 125 transitions. [2022-11-22 02:26:29,636 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 125 transitions. Word has length 38 [2022-11-22 02:26:29,636 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-22 02:26:29,637 INFO L495 AbstractCegarLoop]: Abstraction has 101 states and 125 transitions. [2022-11-22 02:26:29,637 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 43 states, 27 states have (on average 1.6296296296296295) internal successors, (44), 31 states have internal predecessors, (44), 13 states have call successors, (13), 9 states have call predecessors, (13), 14 states have return successors, (14), 13 states have call predecessors, (14), 13 states have call successors, (14) [2022-11-22 02:26:29,637 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 125 transitions. [2022-11-22 02:26:29,638 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-11-22 02:26:29,638 INFO L187 NwaCegarLoop]: Found error trace [2022-11-22 02:26:29,639 INFO L195 NwaCegarLoop]: trace histogram [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] [2022-11-22 02:26:29,647 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2022-11-22 02:26:29,843 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2022-11-22 02:26:29,843 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-22 02:26:29,843 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-22 02:26:29,844 INFO L85 PathProgramCache]: Analyzing trace with hash -167978734, now seen corresponding path program 1 times [2022-11-22 02:26:29,844 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-22 02:26:29,844 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1356158271] [2022-11-22 02:26:29,844 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-22 02:26:29,844 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-22 02:26:29,889 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-22 02:26:29,954 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-11-22 02:26:29,955 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-22 02:26:29,955 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1356158271] [2022-11-22 02:26:29,955 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1356158271] provided 1 perfect and 0 imperfect interpolant sequences [2022-11-22 02:26:29,955 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-11-22 02:26:29,955 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-11-22 02:26:29,956 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [241247979] [2022-11-22 02:26:29,956 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-11-22 02:26:29,956 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-11-22 02:26:29,956 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-22 02:26:29,957 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-11-22 02:26:29,957 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-11-22 02:26:29,957 INFO L87 Difference]: Start difference. First operand 101 states and 125 transitions. Second operand has 4 states, 4 states have (on average 6.75) internal successors, (27), 4 states have internal predecessors, (27), 2 states have call successors, (6), 1 states have call predecessors, (6), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2022-11-22 02:26:30,091 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-22 02:26:30,092 INFO L93 Difference]: Finished difference Result 175 states and 218 transitions. [2022-11-22 02:26:30,092 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-11-22 02:26:30,092 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 6.75) internal successors, (27), 4 states have internal predecessors, (27), 2 states have call successors, (6), 1 states have call predecessors, (6), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) Word has length 40 [2022-11-22 02:26:30,093 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-22 02:26:30,095 INFO L225 Difference]: With dead ends: 175 [2022-11-22 02:26:30,095 INFO L226 Difference]: Without dead ends: 109 [2022-11-22 02:26:30,096 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-11-22 02:26:30,097 INFO L413 NwaCegarLoop]: 50 mSDtfsCounter, 0 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-11-22 02:26:30,098 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 144 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-11-22 02:26:30,099 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 109 states. [2022-11-22 02:26:30,126 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 109 to 107. [2022-11-22 02:26:30,126 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 72 states have (on average 1.2777777777777777) internal successors, (92), 78 states have internal predecessors, (92), 17 states have call successors, (17), 12 states have call predecessors, (17), 15 states have return successors, (22), 17 states have call predecessors, (22), 17 states have call successors, (22) [2022-11-22 02:26:30,129 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 131 transitions. [2022-11-22 02:26:30,130 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 131 transitions. Word has length 40 [2022-11-22 02:26:30,131 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-22 02:26:30,132 INFO L495 AbstractCegarLoop]: Abstraction has 107 states and 131 transitions. [2022-11-22 02:26:30,132 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 6.75) internal successors, (27), 4 states have internal predecessors, (27), 2 states have call successors, (6), 1 states have call predecessors, (6), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2022-11-22 02:26:30,132 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 131 transitions. [2022-11-22 02:26:30,136 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2022-11-22 02:26:30,136 INFO L187 NwaCegarLoop]: Found error trace [2022-11-22 02:26:30,137 INFO L195 NwaCegarLoop]: trace histogram [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] [2022-11-22 02:26:30,137 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2022-11-22 02:26:30,137 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-22 02:26:30,137 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-22 02:26:30,138 INFO L85 PathProgramCache]: Analyzing trace with hash 1456415474, now seen corresponding path program 1 times [2022-11-22 02:26:30,138 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-22 02:26:30,138 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [299890137] [2022-11-22 02:26:30,138 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-22 02:26:30,138 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-22 02:26:30,189 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-22 02:26:36,140 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-11-22 02:26:36,140 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-22 02:26:36,140 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [299890137] [2022-11-22 02:26:36,140 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [299890137] provided 0 perfect and 1 imperfect interpolant sequences [2022-11-22 02:26:36,140 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [816852400] [2022-11-22 02:26:36,141 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-22 02:26:36,141 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-22 02:26:36,141 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 [2022-11-22 02:26:36,146 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-11-22 02:26:36,167 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-11-22 02:26:36,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-22 02:26:36,342 INFO L263 TraceCheckSpWp]: Trace formula consists of 453 conjuncts, 49 conjunts are in the unsatisfiable core [2022-11-22 02:26:36,345 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-11-22 02:26:37,145 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-11-22 02:26:37,145 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-11-22 02:26:37,973 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 16 [2022-11-22 02:26:37,978 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 12 [2022-11-22 02:26:37,997 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-11-22 02:26:37,997 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [816852400] provided 0 perfect and 2 imperfect interpolant sequences [2022-11-22 02:26:37,997 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [959187492] [2022-11-22 02:26:38,000 INFO L159 IcfgInterpreter]: Started Sifa with 36 locations of interest [2022-11-22 02:26:38,001 INFO L166 IcfgInterpreter]: Building call graph [2022-11-22 02:26:38,001 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2022-11-22 02:26:38,001 INFO L176 IcfgInterpreter]: Starting interpretation [2022-11-22 02:26:38,002 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2022-11-22 02:26:38,057 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2022-11-22 02:26:38,064 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 9 [2022-11-22 02:26:38,167 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:38,265 INFO L321 Elim1Store]: treesize reduction 147, result has 22.2 percent of original size [2022-11-22 02:26:38,265 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 49 [2022-11-22 02:26:38,287 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:38,443 INFO L321 Elim1Store]: treesize reduction 128, result has 32.3 percent of original size [2022-11-22 02:26:38,443 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 68 [2022-11-22 02:26:38,479 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:38,621 INFO L321 Elim1Store]: treesize reduction 131, result has 34.8 percent of original size [2022-11-22 02:26:38,621 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 81 treesize of output 70 [2022-11-22 02:26:38,652 INFO L350 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 7 treesize of output 3 [2022-11-22 02:26:38,657 INFO L350 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 7 treesize of output 3 [2022-11-22 02:26:38,668 INFO L350 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 7 treesize of output 3 [2022-11-22 02:26:38,677 INFO L350 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 7 treesize of output 3 [2022-11-22 02:26:38,704 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:38,705 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:38,708 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:26:38,722 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:38,724 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:38,729 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:26:38,779 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:38,781 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:38,781 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:26:38,791 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:38,793 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:38,794 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:26:38,829 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:38,836 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:38,862 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:38,871 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:39,043 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:39,045 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:39,046 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:26:39,055 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:39,057 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:39,058 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:26:39,187 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:39,188 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:39,189 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:26:39,200 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:39,201 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:39,202 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2022-11-22 02:26:39,425 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:39,434 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:39,447 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:39,457 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:39,595 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:39,604 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:39,618 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:39,628 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2022-11-22 02:26:40,517 INFO L321 Elim1Store]: treesize reduction 25, result has 43.2 percent of original size [2022-11-22 02:26:40,517 INFO L350 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 1 case distinctions, treesize of input 35 treesize of output 19 [2022-11-22 02:26:40,525 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:40,665 INFO L321 Elim1Store]: treesize reduction 132, result has 25.8 percent of original size [2022-11-22 02:26:40,665 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 48 treesize of output 59 [2022-11-22 02:26:40,687 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-11-22 02:26:40,837 INFO L321 Elim1Store]: treesize reduction 122, result has 31.5 percent of original size [2022-11-22 02:26:40,837 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 48 treesize of output 69 [2022-11-22 02:26:42,315 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_successful_malloc with input of size 27 for LOIs [2022-11-22 02:26:42,320 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_list_del with input of size 27 for LOIs [2022-11-22 02:26:42,341 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_is_in_set with input of size 41 for LOIs [2022-11-22 02:26:42,406 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_list_add with input of size 34 for LOIs [2022-11-22 02:26:42,451 INFO L197 IcfgInterpreter]: Interpreting procedure __ldv_list_add with input of size 42 for LOIs [2022-11-22 02:26:42,497 INFO L180 IcfgInterpreter]: Interpretation finished [2022-11-22 02:26:50,023 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3498#(and (= (+ 8 |ULTIMATE.start_foo_~me~1#1.offset|) |~#drvlist~0.offset|) (= |~#drvlist~0.offset| 0) (<= 0 (+ |ULTIMATE.start_foo_~N~0#1| 2147483648)) (= |ULTIMATE.start_foo_~__mptr~7#1.base| |ULTIMATE.start_foo_~me~1#1.base|) (= |ULTIMATE.start_ldv_set_empty_#in~s#1.offset| |~#mutexes~0.offset|) (= |ULTIMATE.start_foo_~__mptr~7#1.offset| (select (select |#memory_$Pointer$.offset| |~#drvlist~0.base|) |~#drvlist~0.offset|)) (= |ULTIMATE.start_ldv_list_empty_~head#1.base| |ULTIMATE.start_ldv_list_empty_#in~head#1.base|) (= |ULTIMATE.start_ldv_list_empty_#res#1| |ULTIMATE.start_ldv_set_empty_#res#1|) (= (select (select |#memory_$Pointer$.base| |~#drvlist~0.base|) |~#drvlist~0.offset|) |ULTIMATE.start_foo_~__mptr~7#1.base|) (= |~#mutexes~0.base| 3) (= (ite (and (= (select (select |#memory_$Pointer$.offset| |ULTIMATE.start_ldv_list_empty_~head#1.base|) |ULTIMATE.start_ldv_list_empty_~head#1.offset|) |ULTIMATE.start_ldv_list_empty_~head#1.offset|) (= |ULTIMATE.start_ldv_list_empty_~head#1.base| (select (select |#memory_$Pointer$.base| |ULTIMATE.start_ldv_list_empty_~head#1.base|) |ULTIMATE.start_ldv_list_empty_~head#1.offset|))) 1 0) |ULTIMATE.start_ldv_list_empty_#res#1|) (= |ULTIMATE.start_ldv_set_empty_#res#1| 0) (= |~#mutexes~0.offset| 0) (= |~#mutexes~0.base| |ULTIMATE.start_ldv_set_empty_#in~s#1.base|) (= |ULTIMATE.start_ldv_set_empty_#in~s#1.offset| |ULTIMATE.start_ldv_set_empty_~s#1.offset|) (= |ULTIMATE.start_ldv_set_empty_~s#1.base| |ULTIMATE.start_ldv_list_empty_#in~head#1.base|) (= |ULTIMATE.start_foo_~__mptr~7#1.offset| (+ 8 |ULTIMATE.start_foo_~me~1#1.offset|)) (= |ULTIMATE.start_ldv_list_empty_#in~head#1.offset| |ULTIMATE.start_ldv_list_empty_~head#1.offset|) (= |#NULL.offset| 0) (= |ULTIMATE.start_ldv_set_empty_~s#1.offset| |ULTIMATE.start_ldv_list_empty_#in~head#1.offset|) (= |~#drvlist~0.base| |ULTIMATE.start_foo_~me~1#1.base|) (= |ULTIMATE.start_ldv_set_empty_~s#1.base| |ULTIMATE.start_ldv_set_empty_#in~s#1.base|) (<= |ULTIMATE.start_foo_~N~0#1| 2147483647) (<= 0 |#StackHeapBarrier|) (= 4 |~#drvlist~0.base|) (<= 0 |ULTIMATE.start_foo_~i~0#1|) (= |#NULL.base| 0))' at error location [2022-11-22 02:26:50,023 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2022-11-22 02:26:50,023 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-11-22 02:26:50,024 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 9, 8] total 35 [2022-11-22 02:26:50,024 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1201493502] [2022-11-22 02:26:50,024 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-11-22 02:26:50,025 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2022-11-22 02:26:50,025 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-22 02:26:50,026 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2022-11-22 02:26:50,027 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=240, Invalid=3300, Unknown=0, NotChecked=0, Total=3540 [2022-11-22 02:26:50,028 INFO L87 Difference]: Start difference. First operand 107 states and 131 transitions. Second operand has 35 states, 28 states have (on average 2.7857142857142856) internal successors, (78), 30 states have internal predecessors, (78), 10 states have call successors, (18), 7 states have call predecessors, (18), 12 states have return successors, (18), 10 states have call predecessors, (18), 10 states have call successors, (18) [2022-11-22 02:26:58,827 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-22 02:26:58,827 INFO L93 Difference]: Finished difference Result 302 states and 379 transitions. [2022-11-22 02:26:58,828 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2022-11-22 02:26:58,828 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 28 states have (on average 2.7857142857142856) internal successors, (78), 30 states have internal predecessors, (78), 10 states have call successors, (18), 7 states have call predecessors, (18), 12 states have return successors, (18), 10 states have call predecessors, (18), 10 states have call successors, (18) Word has length 41 [2022-11-22 02:26:58,828 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-22 02:26:58,831 INFO L225 Difference]: With dead ends: 302 [2022-11-22 02:26:58,831 INFO L226 Difference]: Without dead ends: 202 [2022-11-22 02:26:58,835 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 91 SyntacticMatches, 5 SemanticMatches, 101 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2874 ImplicationChecksByTransitivity, 15.6s TimeCoverageRelationStatistics Valid=911, Invalid=9595, Unknown=0, NotChecked=0, Total=10506 [2022-11-22 02:26:58,835 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 368 mSDsluCounter, 517 mSDsCounter, 0 mSdLazyCounter, 1607 mSolverCounterSat, 175 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 382 SdHoareTripleChecker+Valid, 554 SdHoareTripleChecker+Invalid, 1782 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 175 IncrementalHoareTripleChecker+Valid, 1607 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.4s IncrementalHoareTripleChecker+Time [2022-11-22 02:26:58,836 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [382 Valid, 554 Invalid, 1782 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [175 Valid, 1607 Invalid, 0 Unknown, 0 Unchecked, 3.4s Time] [2022-11-22 02:26:58,837 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 202 states. [2022-11-22 02:26:58,868 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 202 to 131. [2022-11-22 02:26:58,869 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 131 states, 93 states have (on average 1.2580645161290323) internal successors, (117), 99 states have internal predecessors, (117), 18 states have call successors, (18), 14 states have call predecessors, (18), 17 states have return successors, (25), 18 states have call predecessors, (25), 18 states have call successors, (25) [2022-11-22 02:26:58,870 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 160 transitions. [2022-11-22 02:26:58,870 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 160 transitions. Word has length 41 [2022-11-22 02:26:58,870 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-22 02:26:58,870 INFO L495 AbstractCegarLoop]: Abstraction has 131 states and 160 transitions. [2022-11-22 02:26:58,871 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 28 states have (on average 2.7857142857142856) internal successors, (78), 30 states have internal predecessors, (78), 10 states have call successors, (18), 7 states have call predecessors, (18), 12 states have return successors, (18), 10 states have call predecessors, (18), 10 states have call successors, (18) [2022-11-22 02:26:58,871 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 160 transitions. [2022-11-22 02:26:58,872 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2022-11-22 02:26:58,872 INFO L187 NwaCegarLoop]: Found error trace [2022-11-22 02:26:58,872 INFO L195 NwaCegarLoop]: trace histogram [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] [2022-11-22 02:26:58,880 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-11-22 02:26:59,079 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-22 02:26:59,079 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-22 02:26:59,079 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-22 02:26:59,079 INFO L85 PathProgramCache]: Analyzing trace with hash -21932279, now seen corresponding path program 1 times [2022-11-22 02:26:59,080 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-22 02:26:59,080 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [471497787] [2022-11-22 02:26:59,080 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-22 02:26:59,080 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-22 02:26:59,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-11-22 02:26:59,396 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-11-22 02:26:59,538 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-11-22 02:26:59,606 INFO L130 FreeRefinementEngine]: Strategy SIFA_TAIPAN found a feasible trace [2022-11-22 02:26:59,606 INFO L359 BasicCegarLoop]: Counterexample is feasible [2022-11-22 02:26:59,608 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION (2 of 3 remaining) [2022-11-22 02:26:59,610 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (1 of 3 remaining) [2022-11-22 02:26:59,611 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION (0 of 3 remaining) [2022-11-22 02:26:59,611 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2022-11-22 02:26:59,617 INFO L444 BasicCegarLoop]: Path program histogram: [2, 1, 1, 1, 1, 1, 1, 1] [2022-11-22 02:26:59,623 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2022-11-22 02:26:59,728 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.11 02:26:59 BoogieIcfgContainer [2022-11-22 02:26:59,729 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-11-22 02:26:59,729 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2022-11-22 02:26:59,730 INFO L271 PluginConnector]: Initializing Witness Printer... [2022-11-22 02:26:59,730 INFO L275 PluginConnector]: Witness Printer initialized [2022-11-22 02:26:59,730 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.11 02:25:26" (3/4) ... [2022-11-22 02:26:59,735 INFO L131 WitnessPrinter]: Generating witness for reachability counterexample [2022-11-22 02:26:59,812 INFO L141 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/witness.graphml [2022-11-22 02:26:59,812 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2022-11-22 02:26:59,814 INFO L158 Benchmark]: Toolchain (without parser) took 94483.39ms. Allocated memory was 121.6MB in the beginning and 499.1MB in the end (delta: 377.5MB). Free memory was 77.3MB in the beginning and 205.5MB in the end (delta: -128.2MB). Peak memory consumption was 250.2MB. Max. memory is 16.1GB. [2022-11-22 02:26:59,814 INFO L158 Benchmark]: CDTParser took 0.31ms. Allocated memory is still 121.6MB. Free memory is still 68.8MB. There was no memory consumed. Max. memory is 16.1GB. [2022-11-22 02:26:59,817 INFO L158 Benchmark]: CACSL2BoogieTranslator took 560.80ms. Allocated memory is still 121.6MB. Free memory was 76.9MB in the beginning and 56.8MB in the end (delta: 20.1MB). Peak memory consumption was 21.0MB. Max. memory is 16.1GB. [2022-11-22 02:26:59,817 INFO L158 Benchmark]: Boogie Procedure Inliner took 53.79ms. Allocated memory is still 121.6MB. Free memory was 56.8MB in the beginning and 54.3MB in the end (delta: 2.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2022-11-22 02:26:59,817 INFO L158 Benchmark]: Boogie Preprocessor took 102.72ms. Allocated memory was 121.6MB in the beginning and 165.7MB in the end (delta: 44.0MB). Free memory was 54.3MB in the beginning and 136.9MB in the end (delta: -82.6MB). Peak memory consumption was 7.2MB. Max. memory is 16.1GB. [2022-11-22 02:26:59,819 INFO L158 Benchmark]: RCFGBuilder took 760.71ms. Allocated memory is still 165.7MB. Free memory was 136.9MB in the beginning and 108.4MB in the end (delta: 28.5MB). Peak memory consumption was 31.8MB. Max. memory is 16.1GB. [2022-11-22 02:26:59,820 INFO L158 Benchmark]: TraceAbstraction took 92915.09ms. Allocated memory was 165.7MB in the beginning and 499.1MB in the end (delta: 333.4MB). Free memory was 107.3MB in the beginning and 210.7MB in the end (delta: -103.4MB). Peak memory consumption was 230.0MB. Max. memory is 16.1GB. [2022-11-22 02:26:59,820 INFO L158 Benchmark]: Witness Printer took 82.66ms. Allocated memory is still 499.1MB. Free memory was 210.7MB in the beginning and 205.5MB in the end (delta: 5.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2022-11-22 02:26:59,824 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.31ms. Allocated memory is still 121.6MB. Free memory is still 68.8MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 560.80ms. Allocated memory is still 121.6MB. Free memory was 76.9MB in the beginning and 56.8MB in the end (delta: 20.1MB). Peak memory consumption was 21.0MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 53.79ms. Allocated memory is still 121.6MB. Free memory was 56.8MB in the beginning and 54.3MB in the end (delta: 2.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 102.72ms. Allocated memory was 121.6MB in the beginning and 165.7MB in the end (delta: 44.0MB). Free memory was 54.3MB in the beginning and 136.9MB in the end (delta: -82.6MB). Peak memory consumption was 7.2MB. Max. memory is 16.1GB. * RCFGBuilder took 760.71ms. Allocated memory is still 165.7MB. Free memory was 136.9MB in the beginning and 108.4MB in the end (delta: 28.5MB). Peak memory consumption was 31.8MB. Max. memory is 16.1GB. * TraceAbstraction took 92915.09ms. Allocated memory was 165.7MB in the beginning and 499.1MB in the end (delta: 333.4MB). Free memory was 107.3MB in the beginning and 210.7MB in the end (delta: -103.4MB). Peak memory consumption was 230.0MB. Max. memory is 16.1GB. * Witness Printer took 82.66ms. Allocated memory is still 499.1MB. Free memory was 210.7MB in the beginning and 205.5MB in the end (delta: 5.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 681]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L669] struct ldv_list_head mutexes = { &(mutexes), &(mutexes) }; [L687] struct ldv_list_head drvlist = { &(drvlist), &(drvlist) }; [L709] CALL foo() [L690] FCALL ldv_initialize() [L691] int i; [L692] int N = __VERIFIER_nondet_int(); [L693] i=0 VAL [drvlist={4:0}, i=0, mutexes={3:0}, N=1] [L693] COND TRUE ilist, &drvlist) VAL [drvlist={4:0}, head={4:0}, mutexes={3:0}, new={5:8}] [L612] EXPR head->next VAL [drvlist={4:0}, head={4:0}, head={4:0}, head->next={4:0}, mutexes={3:0}, new={5:8}, new={5:8}] [L612] CALL __ldv_list_add(new, head, head->next) VAL [drvlist={4:0}, mutexes={3:0}, new={5:8}, next={4:0}, prev={4:0}] [L600] next->prev = new [L601] new->next = next [L602] new->prev = prev [L603] prev->next = new [L612] RET __ldv_list_add(new, head, head->next) VAL [drvlist={4:0}, head={4:0}, head={4:0}, head->next={4:0}, mutexes={3:0}, new={5:8}, new={5:8}] [L695] RET ldv_list_add(&me->list, &drvlist) VAL [drvlist={4:0}, i=0, me={5:0}, mutexes={3:0}, N=1] [L693] i++ VAL [drvlist={4:0}, i=1, me={5:0}, mutexes={3:0}, N=1] [L693] COND FALSE !(inext [L698] const typeof( ((typeof(*me) *)0)->list ) *__mptr = ((&drvlist)->next); [L698] me = ({ const typeof( ((typeof(*me) *)0)->list ) *__mptr = ((&drvlist)->next); (typeof(*me) *)( (char *)__mptr - ((size_t) &((typeof(*me) *)0)->list) );}) VAL [__mptr={5:8}, drvlist={4:0}, i=1, me={5:0}, me={5:0}, mutexes={3:0}, N=1] [L698] COND TRUE &me->list != (&drvlist) [L699] CALL mutex_lock(&me->m) [L673] CALL ldv_is_in_set(m, &mutexes) VAL [drvlist={4:0}, e={5:0}, mutexes={3:0}, s={3:0}] [L658] struct ldv_list_element *m; [L659] EXPR (s)->next [L659] const typeof( ((typeof(*m) *)0)->list ) *__mptr = ((s)->next); [L659] m = ({ const typeof( ((typeof(*m) *)0)->list ) *__mptr = ((s)->next); (typeof(*m) *)( (char *)__mptr - ((size_t) &((typeof(*m) *)0)->list) );}) VAL [__mptr={3:0}, drvlist={4:0}, e={5:0}, e={5:0}, m={3:-4}, mutexes={3:0}, s={3:0}, s={3:0}] [L659] COND FALSE !(&m->list != (s)) [L664] return 0; VAL [\result=0, __mptr={3:0}, drvlist={4:0}, e={5:0}, e={5:0}, m={3:-4}, mutexes={3:0}, s={3:0}, s={3:0}] [L673] RET ldv_is_in_set(m, &mutexes) VAL [drvlist={4:0}, ldv_is_in_set(m, &mutexes)=0, m={5:0}, m={5:0}, mutexes={3:0}] [L673] COND FALSE !(ldv_is_in_set(m, &mutexes)) [L674] CALL ldv_set_add(m, &mutexes) [L640] CALL, EXPR ldv_is_in_set(new, s) VAL [drvlist={4:0}, e={5:0}, mutexes={3:0}, s={3:0}] [L658] struct ldv_list_element *m; [L659] EXPR (s)->next [L659] const typeof( ((typeof(*m) *)0)->list ) *__mptr = ((s)->next); [L659] m = ({ const typeof( ((typeof(*m) *)0)->list ) *__mptr = ((s)->next); (typeof(*m) *)( (char *)__mptr - ((size_t) &((typeof(*m) *)0)->list) );}) VAL [__mptr={3:0}, drvlist={4:0}, e={5:0}, e={5:0}, m={3:-4}, mutexes={3:0}, s={3:0}, s={3:0}] [L659] COND FALSE !(&m->list != (s)) [L664] return 0; VAL [\result=0, __mptr={3:0}, drvlist={4:0}, e={5:0}, e={5:0}, m={3:-4}, mutexes={3:0}, s={3:0}, s={3:0}] [L640] RET, EXPR ldv_is_in_set(new, s) VAL [drvlist={4:0}, ldv_is_in_set(new, s)=0, mutexes={3:0}, new={5:0}, new={5:0}, s={3:0}, s={3:0}] [L640] COND TRUE !ldv_is_in_set(new, s) [L641] struct ldv_list_element *le; VAL [drvlist={4:0}, mutexes={3:0}, new={5:0}, new={5:0}, s={3:0}, s={3:0}] [L642] CALL, EXPR ldv_successful_malloc(sizeof(struct ldv_list_element)) VAL [drvlist={4:0}, mutexes={3:0}] [L580] void *ptr = malloc(size); [L581] CALL assume_abort_if_not(ptr!=0) [L569] COND FALSE !(!cond) [L581] RET assume_abort_if_not(ptr!=0) [L582] return ptr; [L642] RET, EXPR ldv_successful_malloc(sizeof(struct ldv_list_element)) VAL [drvlist={4:0}, ldv_successful_malloc(sizeof(struct ldv_list_element))={-1:0}, mutexes={3:0}, new={5:0}, new={5:0}, s={3:0}, s={3:0}] [L642] le = (struct ldv_list_element*)ldv_successful_malloc(sizeof(struct ldv_list_element)) [L643] le->e = new VAL [drvlist={4:0}, le={-1:0}, mutexes={3:0}, new={5:0}, new={5:0}, s={3:0}, s={3:0}] [L644] CALL ldv_list_add(&le->list, s) VAL [drvlist={4:0}, head={3:0}, mutexes={3:0}, new={-1:4}] [L612] EXPR head->next VAL [drvlist={4:0}, head={3:0}, head={3:0}, head->next={3:0}, mutexes={3:0}, new={-1:4}, new={-1:4}] [L612] CALL __ldv_list_add(new, head, head->next) VAL [drvlist={4:0}, mutexes={3:0}, new={-1:4}, next={3:0}, prev={3:0}] [L600] next->prev = new [L601] new->next = next [L602] new->prev = prev [L603] prev->next = new [L612] RET __ldv_list_add(new, head, head->next) VAL [drvlist={4:0}, head={3:0}, head={3:0}, head->next={3:0}, mutexes={3:0}, new={-1:4}, new={-1:4}] [L644] RET ldv_list_add(&le->list, s) VAL [drvlist={4:0}, le={-1:0}, mutexes={3:0}, new={5:0}, new={5:0}, s={3:0}, s={3:0}] [L674] RET ldv_set_add(m, &mutexes) [L699] RET mutex_lock(&me->m) [L700] CALL ldv_list_del(&me->list) VAL [drvlist={4:0}, mutexes={3:0}] [L620] EXPR entry->prev [L620] EXPR entry->next [L620] CALL __ldv_list_del(entry->prev, entry->next) [L607] next->prev = prev [L608] prev->next = next [L620] RET __ldv_list_del(entry->prev, entry->next) [L700] RET ldv_list_del(&me->list) VAL [__mptr={5:8}, drvlist={4:0}, i=1, me={5:0}, me={5:0}, mutexes={3:0}, N=1] [L698] EXPR (me)->list.next [L698] const typeof( ((typeof(*(me)) *)0)->list ) *__mptr = ((me)->list.next); [L698] me = ({ const typeof( ((typeof(*(me)) *)0)->list ) *__mptr = ((me)->list.next); (typeof(*(me)) *)( (char *)__mptr - ((size_t) &((typeof(*(me)) *)0)->list) );}) VAL [__mptr={5:8}, __mptr={4:0}, drvlist={4:0}, i=1, me={4:-8}, me={5:0}, mutexes={3:0}, N=1] [L698] COND FALSE !(&me->list != (&drvlist)) [L702] EXPR (&drvlist)->next [L702] const typeof( ((typeof(*me) *)0)->list ) *__mptr = ((&drvlist)->next); [L702] me = ({ const typeof( ((typeof(*me) *)0)->list ) *__mptr = ((&drvlist)->next); (typeof(*me) *)( (char *)__mptr - ((size_t) &((typeof(*me) *)0)->list) );}) VAL [__mptr={4:0}, __mptr={5:8}, __mptr={4:0}, drvlist={4:0}, i=1, me={5:0}, me={4:-8}, mutexes={3:0}, N=1] [L702] COND FALSE !(&me->list != (&drvlist)) [L705] CALL ldv_check_final_state() [L681] CALL, EXPR ldv_set_empty(&mutexes) [L667] CALL, EXPR ldv_list_empty(s) [L624] EXPR head->next [L624] return head->next == head; [L667] RET, EXPR ldv_list_empty(s) [L667] return ldv_list_empty(s); [L681] RET, EXPR ldv_set_empty(&mutexes) [L681] COND TRUE !ldv_set_empty(&mutexes) [L681] reach_error() VAL [drvlist={4:0}, mutexes={3:0}] - UnprovableResult [Line: 673]: Unable to prove that call to reach_error is unreachable Unable to prove that call to reach_error is unreachable Reason: Not analyzed. - UnprovableResult [Line: 677]: Unable to prove that call to reach_error is unreachable Unable to prove that call to reach_error is unreachable Reason: Not analyzed. - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 54 locations, 3 error locations. Started 1 CEGAR loops. OverallTime: 92.7s, OverallIterations: 9, TraceHistogramMax: 2, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 22.0s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 25 mSolverCounterUnknown, 1298 SdHoareTripleChecker+Valid, 10.3s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 1284 mSDsluCounter, 2359 SdHoareTripleChecker+Invalid, 9.3s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2008 mSDsCounter, 666 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 5047 IncrementalHoareTripleChecker+Invalid, 5738 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 666 mSolverCounterUnsat, 351 mSDtfsCounter, 5047 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 545 GetRequests, 204 SyntacticMatches, 6 SemanticMatches, 335 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 8098 ImplicationChecksByTransitivity, 48.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=131occurred in iteration=8, InterpolantAutomatonStates: 142, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 8 MinimizatonAttempts, 208 StatesRemovedByMinimization, 7 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.8s SatisfiabilityAnalysisTime, 31.7s InterpolantComputationTime, 366 NumberOfCodeBlocks, 366 NumberOfCodeBlocksAsserted, 15 NumberOfCheckSat, 361 ConstructedInterpolants, 10 QuantifiedInterpolants, 15116 SizeOfPredicates, 94 NumberOfNonLiveVariables, 1470 ConjunctsInSsa, 406 ConjunctsInUnsatCore, 14 InterpolantComputations, 4 PerfectInterpolantSequences, 15/59 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2022-11-22 02:26:59,870 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2949a6e4-a19e-4eb4-9d54-42981f7873f3/bin/utaipan-g80aRyZoba/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE