./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/ldv-linux-3.16-rc1/205_9a_array_unsafes_linux-3.16-rc1.tar.xz-205_9a-drivers--net--ppp--ppp_generic.ko-entry_point.cil.out.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 173e3943 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/ldv-linux-3.16-rc1/205_9a_array_unsafes_linux-3.16-rc1.tar.xz-205_9a-drivers--net--ppp--ppp_generic.ko-entry_point.cil.out.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 64bit --witnessprinter.graph.data.programhash ed18c341b13cb38f54b1bbde59f9cd5a73bcebd88430e5620ebca0060f7baed5 --- Real Ultimate output --- This is Ultimate 0.2.1-dev-173e394 [2021-11-06 14:41:07,961 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-11-06 14:41:07,963 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-11-06 14:41:08,016 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-11-06 14:41:08,017 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-11-06 14:41:08,020 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-11-06 14:41:08,021 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-11-06 14:41:08,023 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-11-06 14:41:08,024 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-11-06 14:41:08,029 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-11-06 14:41:08,029 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-11-06 14:41:08,030 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-11-06 14:41:08,031 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-11-06 14:41:08,033 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-11-06 14:41:08,034 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-11-06 14:41:08,037 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-11-06 14:41:08,043 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-11-06 14:41:08,044 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-11-06 14:41:08,045 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-11-06 14:41:08,048 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-11-06 14:41:08,050 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-11-06 14:41:08,052 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-11-06 14:41:08,053 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-11-06 14:41:08,053 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-11-06 14:41:08,055 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-11-06 14:41:08,056 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-11-06 14:41:08,057 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-11-06 14:41:08,057 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-11-06 14:41:08,058 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-11-06 14:41:08,059 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-11-06 14:41:08,059 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-11-06 14:41:08,059 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-11-06 14:41:08,060 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-11-06 14:41:08,061 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-11-06 14:41:08,062 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-11-06 14:41:08,062 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-11-06 14:41:08,063 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-11-06 14:41:08,063 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-11-06 14:41:08,063 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-11-06 14:41:08,064 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-11-06 14:41:08,064 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-11-06 14:41:08,065 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf [2021-11-06 14:41:08,091 INFO L113 SettingsManager]: Loading preferences was successful [2021-11-06 14:41:08,096 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-11-06 14:41:08,096 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-11-06 14:41:08,097 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-11-06 14:41:08,098 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-11-06 14:41:08,098 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-11-06 14:41:08,098 INFO L138 SettingsManager]: * Use SBE=true [2021-11-06 14:41:08,098 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-11-06 14:41:08,098 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-11-06 14:41:08,098 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-11-06 14:41:08,099 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-11-06 14:41:08,099 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-11-06 14:41:08,100 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-11-06 14:41:08,100 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-11-06 14:41:08,100 INFO L138 SettingsManager]: * Use constant arrays=true [2021-11-06 14:41:08,100 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-11-06 14:41:08,100 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-11-06 14:41:08,100 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-11-06 14:41:08,100 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-11-06 14:41:08,101 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-06 14:41:08,101 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-11-06 14:41:08,101 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-11-06 14:41:08,101 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-11-06 14:41:08,101 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-11-06 14:41:08,101 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-11-06 14:41:08,102 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2021-11-06 14:41:08,102 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2021-11-06 14:41:08,102 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-11-06 14:41:08,102 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-11-06 14:41:08,102 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:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.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 -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> ed18c341b13cb38f54b1bbde59f9cd5a73bcebd88430e5620ebca0060f7baed5 [2021-11-06 14:41:08,255 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-11-06 14:41:08,276 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-11-06 14:41:08,278 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-11-06 14:41:08,279 INFO L271 PluginConnector]: Initializing CDTParser... [2021-11-06 14:41:08,280 INFO L275 PluginConnector]: CDTParser initialized [2021-11-06 14:41:08,280 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/ldv-linux-3.16-rc1/205_9a_array_unsafes_linux-3.16-rc1.tar.xz-205_9a-drivers--net--ppp--ppp_generic.ko-entry_point.cil.out.i [2021-11-06 14:41:08,325 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/871438ef4/dbf1d383b7ad4e6cb3fbaf29a9dfc16e/FLAGdd36f370e [2021-11-06 14:41:08,960 INFO L306 CDTParser]: Found 1 translation units. [2021-11-06 14:41:08,961 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-linux-3.16-rc1/205_9a_array_unsafes_linux-3.16-rc1.tar.xz-205_9a-drivers--net--ppp--ppp_generic.ko-entry_point.cil.out.i [2021-11-06 14:41:09,032 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/871438ef4/dbf1d383b7ad4e6cb3fbaf29a9dfc16e/FLAGdd36f370e [2021-11-06 14:41:09,306 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/871438ef4/dbf1d383b7ad4e6cb3fbaf29a9dfc16e [2021-11-06 14:41:09,308 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-11-06 14:41:09,310 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-11-06 14:41:09,312 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-11-06 14:41:09,312 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-11-06 14:41:09,314 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-11-06 14:41:09,315 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 02:41:09" (1/1) ... [2021-11-06 14:41:09,316 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1d4450e0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:41:09, skipping insertion in model container [2021-11-06 14:41:09,316 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 02:41:09" (1/1) ... [2021-11-06 14:41:09,321 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-11-06 14:41:09,419 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-11-06 14:41:10,465 WARN L228 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-linux-3.16-rc1/205_9a_array_unsafes_linux-3.16-rc1.tar.xz-205_9a-drivers--net--ppp--ppp_generic.ko-entry_point.cil.out.i[198800,198813] [2021-11-06 14:41:10,990 INFO L206 PostProcessor]: Analyzing one entry point: main [2021-11-06 14:41:11,031 INFO L203 MainTranslator]: Completed pre-run [2021-11-06 14:41:11,160 WARN L228 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-linux-3.16-rc1/205_9a_array_unsafes_linux-3.16-rc1.tar.xz-205_9a-drivers--net--ppp--ppp_generic.ko-entry_point.cil.out.i[198800,198813] [2021-11-06 14:41:11,280 INFO L206 PostProcessor]: Analyzing one entry point: main [2021-11-06 14:41:11,382 INFO L208 MainTranslator]: Completed translation [2021-11-06 14:41:11,383 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:41:11 WrapperNode [2021-11-06 14:41:11,383 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-11-06 14:41:11,384 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-11-06 14:41:11,384 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-11-06 14:41:11,385 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-11-06 14:41:11,389 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:41:11" (1/1) ... [2021-11-06 14:41:11,463 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:41:11" (1/1) ... [2021-11-06 14:41:12,232 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-11-06 14:41:12,233 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-11-06 14:41:12,233 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-11-06 14:41:12,233 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-11-06 14:41:12,239 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:41:11" (1/1) ... [2021-11-06 14:41:12,239 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:41:11" (1/1) ... [2021-11-06 14:41:12,522 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:41:11" (1/1) ... [2021-11-06 14:41:12,523 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:41:11" (1/1) ... [2021-11-06 14:41:12,994 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:41:11" (1/1) ... [2021-11-06 14:41:13,097 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:41:11" (1/1) ... [2021-11-06 14:41:13,179 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:41:11" (1/1) ... [2021-11-06 14:41:13,308 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-11-06 14:41:13,309 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-11-06 14:41:13,309 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-11-06 14:41:13,309 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-11-06 14:41:13,310 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:41:11" (1/1) ... [2021-11-06 14:41:13,315 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-06 14:41:13,321 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-11-06 14:41:13,330 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2021-11-06 14:41:13,336 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2021-11-06 14:41:13,354 INFO L130 BoogieDeclarations]: Found specification of procedure ##fun~$Pointer$~X~int~X~int~TO~int [2021-11-06 14:41:13,354 INFO L138 BoogieDeclarations]: Found implementation of procedure ##fun~$Pointer$~X~int~X~int~TO~int [2021-11-06 14:41:13,354 INFO L130 BoogieDeclarations]: Found specification of procedure __xchg_wrong_size [2021-11-06 14:41:13,355 INFO L130 BoogieDeclarations]: Found specification of procedure read~unchecked~$Pointer$ [2021-11-06 14:41:13,355 INFO L130 BoogieDeclarations]: Found specification of procedure write~unchecked~$Pointer$ [2021-11-06 14:41:13,355 INFO L130 BoogieDeclarations]: Found specification of procedure ppp_xmit_process [2021-11-06 14:41:13,355 INFO L138 BoogieDeclarations]: Found implementation of procedure ppp_xmit_process [2021-11-06 14:41:13,355 INFO L130 BoogieDeclarations]: Found specification of procedure ppp_destroy_interface [2021-11-06 14:41:13,355 INFO L138 BoogieDeclarations]: Found implementation of procedure ppp_destroy_interface [2021-11-06 14:41:13,355 INFO L130 BoogieDeclarations]: Found specification of procedure ppp_push [2021-11-06 14:41:13,356 INFO L138 BoogieDeclarations]: Found implementation of procedure ppp_push [2021-11-06 14:41:13,356 INFO L130 BoogieDeclarations]: Found specification of procedure ppp_release [2021-11-06 14:41:13,356 INFO L138 BoogieDeclarations]: Found implementation of procedure ppp_release [2021-11-06 14:41:13,356 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2021-11-06 14:41:13,356 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2021-11-06 14:41:13,356 INFO L130 BoogieDeclarations]: Found specification of procedure ppp_send_frame [2021-11-06 14:41:13,356 INFO L138 BoogieDeclarations]: Found implementation of procedure ppp_send_frame [2021-11-06 14:41:13,356 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-11-06 14:41:13,356 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2021-11-06 14:41:13,357 INFO L130 BoogieDeclarations]: Found specification of procedure ppp_channel_push [2021-11-06 14:41:13,357 INFO L138 BoogieDeclarations]: Found implementation of procedure ppp_channel_push [2021-11-06 14:41:13,357 INFO L130 BoogieDeclarations]: Found specification of procedure read~unchecked~int [2021-11-06 14:41:13,357 INFO L130 BoogieDeclarations]: Found specification of procedure ppp_disconnect_channel [2021-11-06 14:41:13,357 INFO L138 BoogieDeclarations]: Found implementation of procedure ppp_disconnect_channel [2021-11-06 14:41:13,357 INFO L130 BoogieDeclarations]: Found specification of procedure write~unchecked~int [2021-11-06 14:41:13,357 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2021-11-06 14:41:13,357 INFO L130 BoogieDeclarations]: Found specification of procedure ppp_output_wakeup [2021-11-06 14:41:13,358 INFO L138 BoogieDeclarations]: Found implementation of procedure ppp_output_wakeup [2021-11-06 14:41:13,358 INFO L130 BoogieDeclarations]: Found specification of procedure ppp_unregister_channel [2021-11-06 14:41:13,358 INFO L138 BoogieDeclarations]: Found implementation of procedure ppp_unregister_channel [2021-11-06 14:41:13,358 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2021-11-06 14:41:13,358 INFO L130 BoogieDeclarations]: Found specification of procedure ppp_ccp_closed [2021-11-06 14:41:13,358 INFO L138 BoogieDeclarations]: Found implementation of procedure ppp_ccp_closed [2021-11-06 14:41:13,358 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2021-11-06 14:41:13,358 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2021-11-06 14:41:13,358 INFO L130 BoogieDeclarations]: Found specification of procedure __bad_percpu_size [2021-11-06 14:41:13,359 INFO L130 BoogieDeclarations]: Found specification of procedure ##fun~$Pointer$~TO~VOID [2021-11-06 14:41:13,359 INFO L138 BoogieDeclarations]: Found implementation of procedure ##fun~$Pointer$~TO~VOID [2021-11-06 14:41:13,359 INFO L130 BoogieDeclarations]: Found specification of procedure ppp_mp_explode [2021-11-06 14:41:13,359 INFO L138 BoogieDeclarations]: Found implementation of procedure ppp_mp_explode [2021-11-06 14:41:13,359 INFO L130 BoogieDeclarations]: Found specification of procedure ##fun~$Pointer$~X~$Pointer$~TO~int [2021-11-06 14:41:13,359 INFO L138 BoogieDeclarations]: Found implementation of procedure ##fun~$Pointer$~X~$Pointer$~TO~int [2021-11-06 14:41:13,359 INFO L130 BoogieDeclarations]: Found specification of procedure ppp_ioctl [2021-11-06 14:41:13,360 INFO L138 BoogieDeclarations]: Found implementation of procedure ppp_ioctl [2021-11-06 14:41:13,360 INFO L130 BoogieDeclarations]: Found specification of procedure ppp_ccp_peek [2021-11-06 14:41:13,360 INFO L138 BoogieDeclarations]: Found implementation of procedure ppp_ccp_peek [2021-11-06 14:41:13,360 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-11-06 14:41:13,360 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-11-06 14:41:13,360 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-11-06 14:41:29,818 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-11-06 14:41:29,818 INFO L299 CfgBuilder]: Removed 7944 assume(true) statements. [2021-11-06 14:41:29,825 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 02:41:29 BoogieIcfgContainer [2021-11-06 14:41:29,826 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-11-06 14:41:29,827 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-11-06 14:41:29,827 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-11-06 14:41:29,838 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-11-06 14:41:29,838 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.11 02:41:09" (1/3) ... [2021-11-06 14:41:29,839 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3a4a3702 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 02:41:29, skipping insertion in model container [2021-11-06 14:41:29,839 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:41:11" (2/3) ... [2021-11-06 14:41:29,839 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3a4a3702 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 02:41:29, skipping insertion in model container [2021-11-06 14:41:29,839 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 02:41:29" (3/3) ... [2021-11-06 14:41:29,840 INFO L111 eAbstractionObserver]: Analyzing ICFG 205_9a_array_unsafes_linux-3.16-rc1.tar.xz-205_9a-drivers--net--ppp--ppp_generic.ko-entry_point.cil.out.i [2021-11-06 14:41:29,843 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-11-06 14:41:29,844 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-11-06 14:41:29,901 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-11-06 14:41:29,905 INFO L339 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=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, mLoopAccelerationTechnique=FAST_UPR [2021-11-06 14:41:29,905 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-11-06 14:41:29,992 INFO L276 IsEmpty]: Start isEmpty. Operand has 8551 states, 8460 states have (on average 1.5256501182033098) internal successors, (12907), 8486 states have internal predecessors, (12907), 73 states have call successors, (73), 16 states have call predecessors, (73), 16 states have return successors, (73), 69 states have call predecessors, (73), 73 states have call successors, (73) [2021-11-06 14:41:30,001 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2021-11-06 14:41:30,002 INFO L505 BasicCegarLoop]: Found error trace [2021-11-06 14:41:30,002 INFO L513 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-06 14:41:30,003 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-06 14:41:30,006 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-06 14:41:30,006 INFO L85 PathProgramCache]: Analyzing trace with hash 1904356284, now seen corresponding path program 1 times [2021-11-06 14:41:30,011 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-11-06 14:41:30,011 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1046374421] [2021-11-06 14:41:30,012 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-06 14:41:30,012 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-06 14:41:30,292 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-06 14:41:30,464 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-06 14:41:30,464 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-11-06 14:41:30,465 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1046374421] [2021-11-06 14:41:30,465 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1046374421] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-06 14:41:30,465 INFO L186 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-11-06 14:41:30,465 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-11-06 14:41:30,466 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2008241710] [2021-11-06 14:41:30,469 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-11-06 14:41:30,469 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-11-06 14:41:30,476 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-11-06 14:41:30,477 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-11-06 14:41:30,492 INFO L87 Difference]: Start difference. First operand has 8551 states, 8460 states have (on average 1.5256501182033098) internal successors, (12907), 8486 states have internal predecessors, (12907), 73 states have call successors, (73), 16 states have call predecessors, (73), 16 states have return successors, (73), 69 states have call predecessors, (73), 73 states have call successors, (73) Second operand has 5 states, 5 states have (on average 7.0) internal successors, (35), 5 states have internal predecessors, (35), 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) [2021-11-06 14:41:34,264 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-06 14:41:34,264 INFO L93 Difference]: Finished difference Result 25571 states and 39270 transitions. [2021-11-06 14:41:34,265 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-11-06 14:41:34,266 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 7.0) internal successors, (35), 5 states have internal predecessors, (35), 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 35 [2021-11-06 14:41:34,266 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-06 14:41:34,357 INFO L225 Difference]: With dead ends: 25571 [2021-11-06 14:41:34,358 INFO L226 Difference]: Without dead ends: 16898 [2021-11-06 14:41:34,406 INFO L786 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2021-11-06 14:41:34,441 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16898 states. [2021-11-06 14:41:34,784 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16898 to 16186. [2021-11-06 14:41:34,820 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16186 states, 16007 states have (on average 1.3879552695695634) internal successors, (22217), 16057 states have internal predecessors, (22217), 146 states have call successors, (146), 32 states have call predecessors, (146), 32 states have return successors, (219), 138 states have call predecessors, (219), 146 states have call successors, (219) [2021-11-06 14:41:34,863 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16186 states to 16186 states and 22582 transitions. [2021-11-06 14:41:34,865 INFO L78 Accepts]: Start accepts. Automaton has 16186 states and 22582 transitions. Word has length 35 [2021-11-06 14:41:34,865 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-06 14:41:34,865 INFO L470 AbstractCegarLoop]: Abstraction has 16186 states and 22582 transitions. [2021-11-06 14:41:34,866 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 7.0) internal successors, (35), 5 states have internal predecessors, (35), 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) [2021-11-06 14:41:34,866 INFO L276 IsEmpty]: Start isEmpty. Operand 16186 states and 22582 transitions. [2021-11-06 14:41:34,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2021-11-06 14:41:34,874 INFO L505 BasicCegarLoop]: Found error trace [2021-11-06 14:41:34,874 INFO L513 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-06 14:41:34,875 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-11-06 14:41:34,875 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-06 14:41:34,875 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-06 14:41:34,876 INFO L85 PathProgramCache]: Analyzing trace with hash 1149088240, now seen corresponding path program 1 times [2021-11-06 14:41:34,876 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-11-06 14:41:34,876 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2076222578] [2021-11-06 14:41:34,876 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-06 14:41:34,876 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-06 14:41:34,933 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-06 14:41:35,010 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-06 14:41:35,010 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-11-06 14:41:35,010 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2076222578] [2021-11-06 14:41:35,011 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2076222578] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-06 14:41:35,011 INFO L186 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-11-06 14:41:35,011 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-11-06 14:41:35,011 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1669950259] [2021-11-06 14:41:35,012 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-11-06 14:41:35,012 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-11-06 14:41:35,012 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-11-06 14:41:35,013 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-11-06 14:41:35,013 INFO L87 Difference]: Start difference. First operand 16186 states and 22582 transitions. Second operand has 3 states, 3 states have (on average 18.333333333333332) internal successors, (55), 3 states have internal predecessors, (55), 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) [2021-11-06 14:41:35,648 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-06 14:41:35,649 INFO L93 Difference]: Finished difference Result 45840 states and 64262 transitions. [2021-11-06 14:41:35,649 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-11-06 14:41:35,649 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 18.333333333333332) internal successors, (55), 3 states have internal predecessors, (55), 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 55 [2021-11-06 14:41:35,650 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-06 14:41:35,764 INFO L225 Difference]: With dead ends: 45840 [2021-11-06 14:41:35,764 INFO L226 Difference]: Without dead ends: 29729 [2021-11-06 14:41:35,805 INFO L786 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-11-06 14:41:35,840 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29729 states. [2021-11-06 14:41:36,301 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29729 to 28212. [2021-11-06 14:41:36,339 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28212 states, 27863 states have (on average 1.3924559451602483) internal successors, (38798), 27959 states have internal predecessors, (38798), 284 states have call successors, (284), 64 states have call predecessors, (284), 64 states have return successors, (614), 266 states have call predecessors, (614), 284 states have call successors, (614) [2021-11-06 14:41:36,407 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28212 states to 28212 states and 39696 transitions. [2021-11-06 14:41:36,409 INFO L78 Accepts]: Start accepts. Automaton has 28212 states and 39696 transitions. Word has length 55 [2021-11-06 14:41:36,409 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-06 14:41:36,409 INFO L470 AbstractCegarLoop]: Abstraction has 28212 states and 39696 transitions. [2021-11-06 14:41:36,410 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 18.333333333333332) internal successors, (55), 3 states have internal predecessors, (55), 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) [2021-11-06 14:41:36,410 INFO L276 IsEmpty]: Start isEmpty. Operand 28212 states and 39696 transitions. [2021-11-06 14:41:36,415 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2021-11-06 14:41:36,415 INFO L505 BasicCegarLoop]: Found error trace [2021-11-06 14:41:36,416 INFO L513 BasicCegarLoop]: 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-06 14:41:36,416 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2021-11-06 14:41:36,416 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-06 14:41:36,416 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-06 14:41:36,417 INFO L85 PathProgramCache]: Analyzing trace with hash -1727795715, now seen corresponding path program 1 times [2021-11-06 14:41:36,417 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-11-06 14:41:36,417 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1313970426] [2021-11-06 14:41:36,417 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-06 14:41:36,417 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-06 14:41:36,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-06 14:41:36,582 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-06 14:41:36,582 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-11-06 14:41:36,583 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1313970426] [2021-11-06 14:41:36,583 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1313970426] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-06 14:41:36,583 INFO L186 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-11-06 14:41:36,583 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-11-06 14:41:36,583 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [298568302] [2021-11-06 14:41:36,584 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-11-06 14:41:36,584 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-11-06 14:41:36,584 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-11-06 14:41:36,585 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-11-06 14:41:36,585 INFO L87 Difference]: Start difference. First operand 28212 states and 39696 transitions. Second operand has 3 states, 3 states have (on average 19.333333333333332) internal successors, (58), 3 states have internal predecessors, (58), 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) [2021-11-06 14:41:37,477 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-06 14:41:37,477 INFO L93 Difference]: Finished difference Result 79690 states and 111922 transitions. [2021-11-06 14:41:37,478 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-11-06 14:41:37,478 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 19.333333333333332) internal successors, (58), 3 states have internal predecessors, (58), 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 58 [2021-11-06 14:41:37,478 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-06 14:41:37,649 INFO L225 Difference]: With dead ends: 79690 [2021-11-06 14:41:37,650 INFO L226 Difference]: Without dead ends: 51553 [2021-11-06 14:41:37,726 INFO L786 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-11-06 14:41:37,773 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51553 states. [2021-11-06 14:41:38,900 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51553 to 51534. [2021-11-06 14:41:38,958 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51534 states, 50897 states have (on average 1.3883136530640312) internal successors, (70661), 51069 states have internal predecessors, (70661), 516 states have call successors, (516), 120 states have call predecessors, (516), 120 states have return successors, (1108), 488 states have call predecessors, (1108), 516 states have call successors, (1108) [2021-11-06 14:41:39,077 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51534 states to 51534 states and 72285 transitions. [2021-11-06 14:41:39,080 INFO L78 Accepts]: Start accepts. Automaton has 51534 states and 72285 transitions. Word has length 58 [2021-11-06 14:41:39,081 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-06 14:41:39,081 INFO L470 AbstractCegarLoop]: Abstraction has 51534 states and 72285 transitions. [2021-11-06 14:41:39,081 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 19.333333333333332) internal successors, (58), 3 states have internal predecessors, (58), 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) [2021-11-06 14:41:39,081 INFO L276 IsEmpty]: Start isEmpty. Operand 51534 states and 72285 transitions. [2021-11-06 14:41:39,086 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2021-11-06 14:41:39,087 INFO L505 BasicCegarLoop]: Found error trace [2021-11-06 14:41:39,087 INFO L513 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-06 14:41:39,087 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2021-11-06 14:41:39,088 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-06 14:41:39,088 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-06 14:41:39,088 INFO L85 PathProgramCache]: Analyzing trace with hash 1478756629, now seen corresponding path program 1 times [2021-11-06 14:41:39,089 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-11-06 14:41:39,089 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [110108518] [2021-11-06 14:41:39,089 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-06 14:41:39,089 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-06 14:41:39,151 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-06 14:41:39,241 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-11-06 14:41:39,241 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-11-06 14:41:39,241 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [110108518] [2021-11-06 14:41:39,243 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [110108518] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-06 14:41:39,243 INFO L186 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-11-06 14:41:39,243 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-11-06 14:41:39,244 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2132018646] [2021-11-06 14:41:39,244 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-11-06 14:41:39,244 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-11-06 14:41:39,244 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-11-06 14:41:39,245 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-11-06 14:41:39,245 INFO L87 Difference]: Start difference. First operand 51534 states and 72285 transitions. Second operand has 3 states, 3 states have (on average 26.333333333333332) internal successors, (79), 3 states have internal predecessors, (79), 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) [2021-11-06 14:41:40,213 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-06 14:41:40,214 INFO L93 Difference]: Finished difference Result 102998 states and 144491 transitions. [2021-11-06 14:41:40,214 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-11-06 14:41:40,214 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 26.333333333333332) internal successors, (79), 3 states have internal predecessors, (79), 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 81 [2021-11-06 14:41:40,214 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-06 14:41:40,368 INFO L225 Difference]: With dead ends: 102998 [2021-11-06 14:41:40,368 INFO L226 Difference]: Without dead ends: 51539 [2021-11-06 14:41:40,467 INFO L786 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-11-06 14:41:40,509 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51539 states. [2021-11-06 14:41:41,515 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51539 to 51534. [2021-11-06 14:41:41,575 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51534 states, 50897 states have (on average 1.3881564728765938) internal successors, (70653), 51069 states have internal predecessors, (70653), 516 states have call successors, (516), 120 states have call predecessors, (516), 120 states have return successors, (1108), 488 states have call predecessors, (1108), 516 states have call successors, (1108) [2021-11-06 14:41:41,686 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51534 states to 51534 states and 72277 transitions. [2021-11-06 14:41:41,688 INFO L78 Accepts]: Start accepts. Automaton has 51534 states and 72277 transitions. Word has length 81 [2021-11-06 14:41:41,688 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-06 14:41:41,688 INFO L470 AbstractCegarLoop]: Abstraction has 51534 states and 72277 transitions. [2021-11-06 14:41:41,689 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 26.333333333333332) internal successors, (79), 3 states have internal predecessors, (79), 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) [2021-11-06 14:41:41,689 INFO L276 IsEmpty]: Start isEmpty. Operand 51534 states and 72277 transitions. [2021-11-06 14:41:41,694 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2021-11-06 14:41:41,695 INFO L505 BasicCegarLoop]: Found error trace [2021-11-06 14:41:41,695 INFO L513 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-06 14:41:41,695 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2021-11-06 14:41:41,695 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-06 14:41:41,696 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-06 14:41:41,696 INFO L85 PathProgramCache]: Analyzing trace with hash -835888805, now seen corresponding path program 1 times [2021-11-06 14:41:41,696 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-11-06 14:41:41,696 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [406638933] [2021-11-06 14:41:41,696 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-06 14:41:41,696 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-06 14:41:41,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-06 14:41:41,849 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-11-06 14:41:41,849 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-11-06 14:41:41,850 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [406638933] [2021-11-06 14:41:41,850 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [406638933] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-06 14:41:41,850 INFO L186 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-11-06 14:41:41,850 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-11-06 14:41:41,850 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1043547337] [2021-11-06 14:41:41,852 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-11-06 14:41:41,853 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-11-06 14:41:41,854 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-11-06 14:41:41,854 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-11-06 14:41:41,854 INFO L87 Difference]: Start difference. First operand 51534 states and 72277 transitions. Second operand has 4 states, 4 states have (on average 20.25) internal successors, (81), 4 states have internal predecessors, (81), 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) [2021-11-06 14:41:45,205 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-06 14:41:45,205 INFO L93 Difference]: Finished difference Result 205115 states and 288349 transitions. [2021-11-06 14:41:45,205 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-11-06 14:41:45,206 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 20.25) internal successors, (81), 4 states have internal predecessors, (81), 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 83 [2021-11-06 14:41:45,206 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-06 14:41:45,659 INFO L225 Difference]: With dead ends: 205115 [2021-11-06 14:41:45,659 INFO L226 Difference]: Without dead ends: 153656 [2021-11-06 14:41:45,769 INFO L786 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2021-11-06 14:41:45,908 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 153656 states. [2021-11-06 14:41:47,809 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 153656 to 52110. [2021-11-06 14:41:47,862 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52110 states, 51473 states have (on average 1.3838128727682475) internal successors, (71229), 51645 states have internal predecessors, (71229), 516 states have call successors, (516), 120 states have call predecessors, (516), 120 states have return successors, (1108), 488 states have call predecessors, (1108), 516 states have call successors, (1108) [2021-11-06 14:41:47,966 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52110 states to 52110 states and 72853 transitions. [2021-11-06 14:41:47,970 INFO L78 Accepts]: Start accepts. Automaton has 52110 states and 72853 transitions. Word has length 83 [2021-11-06 14:41:47,970 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-06 14:41:47,970 INFO L470 AbstractCegarLoop]: Abstraction has 52110 states and 72853 transitions. [2021-11-06 14:41:47,970 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 20.25) internal successors, (81), 4 states have internal predecessors, (81), 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) [2021-11-06 14:41:47,970 INFO L276 IsEmpty]: Start isEmpty. Operand 52110 states and 72853 transitions. [2021-11-06 14:41:47,977 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2021-11-06 14:41:47,977 INFO L505 BasicCegarLoop]: Found error trace [2021-11-06 14:41:47,977 INFO L513 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-06 14:41:47,977 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2021-11-06 14:41:47,978 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-06 14:41:47,978 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-06 14:41:47,978 INFO L85 PathProgramCache]: Analyzing trace with hash -379160658, now seen corresponding path program 1 times [2021-11-06 14:41:47,978 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-11-06 14:41:47,978 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [12361416] [2021-11-06 14:41:47,978 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-06 14:41:47,979 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-06 14:41:48,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-06 14:41:48,148 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-11-06 14:41:48,149 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-11-06 14:41:48,149 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [12361416] [2021-11-06 14:41:48,149 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [12361416] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-06 14:41:48,149 INFO L186 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-11-06 14:41:48,149 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2021-11-06 14:41:48,149 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1466318670] [2021-11-06 14:41:48,150 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2021-11-06 14:41:48,150 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-11-06 14:41:48,150 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-11-06 14:41:48,150 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2021-11-06 14:41:48,151 INFO L87 Difference]: Start difference. First operand 52110 states and 72853 transitions. Second operand has 9 states, 9 states have (on average 9.777777777777779) internal successors, (88), 9 states have internal predecessors, (88), 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) [2021-11-06 14:42:01,224 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-06 14:42:01,224 INFO L93 Difference]: Finished difference Result 407297 states and 571981 transitions. [2021-11-06 14:42:01,225 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2021-11-06 14:42:01,225 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 9.777777777777779) internal successors, (88), 9 states have internal predecessors, (88), 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 90 [2021-11-06 14:42:01,225 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-06 14:42:02,336 INFO L225 Difference]: With dead ends: 407297 [2021-11-06 14:42:02,336 INFO L226 Difference]: Without dead ends: 355262 [2021-11-06 14:42:02,717 INFO L786 BasicCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 296 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=312, Invalid=948, Unknown=0, NotChecked=0, Total=1260 [2021-11-06 14:42:02,993 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 355262 states. [2021-11-06 14:42:06,201 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 355262 to 52126. [2021-11-06 14:42:06,250 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52126 states, 51489 states have (on average 1.383693604459205) internal successors, (71245), 51661 states have internal predecessors, (71245), 516 states have call successors, (516), 120 states have call predecessors, (516), 120 states have return successors, (1108), 488 states have call predecessors, (1108), 516 states have call successors, (1108) [2021-11-06 14:42:06,357 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52126 states to 52126 states and 72869 transitions. [2021-11-06 14:42:06,362 INFO L78 Accepts]: Start accepts. Automaton has 52126 states and 72869 transitions. Word has length 90 [2021-11-06 14:42:06,363 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-06 14:42:06,363 INFO L470 AbstractCegarLoop]: Abstraction has 52126 states and 72869 transitions. [2021-11-06 14:42:06,363 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 9.777777777777779) internal successors, (88), 9 states have internal predecessors, (88), 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) [2021-11-06 14:42:06,363 INFO L276 IsEmpty]: Start isEmpty. Operand 52126 states and 72869 transitions. [2021-11-06 14:42:06,369 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2021-11-06 14:42:06,369 INFO L505 BasicCegarLoop]: Found error trace [2021-11-06 14:42:06,369 INFO L513 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-06 14:42:06,370 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2021-11-06 14:42:06,370 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-06 14:42:06,370 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-06 14:42:06,370 INFO L85 PathProgramCache]: Analyzing trace with hash 326572585, now seen corresponding path program 1 times [2021-11-06 14:42:06,370 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-11-06 14:42:06,371 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [980504847] [2021-11-06 14:42:06,371 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-06 14:42:06,371 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-06 14:42:06,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-06 14:42:06,529 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 15 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-06 14:42:06,530 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-11-06 14:42:06,530 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [980504847] [2021-11-06 14:42:06,531 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [980504847] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-06 14:42:06,531 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1049672419] [2021-11-06 14:42:06,531 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-06 14:42:06,531 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-06 14:42:06,531 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-11-06 14:42:06,532 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-06 14:42:06,535 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-11-06 14:42:07,459 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-06 14:42:07,472 INFO L263 TraceCheckSpWp]: Trace formula consists of 2443 conjuncts, 2 conjunts are in the unsatisfiable core [2021-11-06 14:42:07,481 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-06 14:42:07,700 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-11-06 14:42:07,701 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1049672419] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-06 14:42:07,701 INFO L186 FreeRefinementEngine]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2021-11-06 14:42:07,701 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [6] total 7 [2021-11-06 14:42:07,701 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1577431018] [2021-11-06 14:42:07,701 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-11-06 14:42:07,702 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-11-06 14:42:07,702 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-11-06 14:42:07,702 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2021-11-06 14:42:07,702 INFO L87 Difference]: Start difference. First operand 52126 states and 72869 transitions. Second operand has 3 states, 3 states have (on average 30.0) internal successors, (90), 3 states have internal predecessors, (90), 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) [2021-11-06 14:42:11,810 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-06 14:42:11,811 INFO L93 Difference]: Finished difference Result 104123 states and 145660 transitions. [2021-11-06 14:42:11,811 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-11-06 14:42:11,811 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 30.0) internal successors, (90), 3 states have internal predecessors, (90), 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 92 [2021-11-06 14:42:11,811 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-06 14:42:11,943 INFO L225 Difference]: With dead ends: 104123 [2021-11-06 14:42:11,943 INFO L226 Difference]: Without dead ends: 51893 [2021-11-06 14:42:12,022 INFO L786 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 92 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2021-11-06 14:42:12,070 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51893 states. [2021-11-06 14:42:13,735 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51893 to 51893. [2021-11-06 14:42:13,793 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51893 states, 51256 states have (on average 1.384442796940846) internal successors, (70961), 51428 states have internal predecessors, (70961), 516 states have call successors, (516), 120 states have call predecessors, (516), 120 states have return successors, (1108), 488 states have call predecessors, (1108), 516 states have call successors, (1108) [2021-11-06 14:42:13,912 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51893 states to 51893 states and 72585 transitions. [2021-11-06 14:42:13,915 INFO L78 Accepts]: Start accepts. Automaton has 51893 states and 72585 transitions. Word has length 92 [2021-11-06 14:42:13,916 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-06 14:42:13,916 INFO L470 AbstractCegarLoop]: Abstraction has 51893 states and 72585 transitions. [2021-11-06 14:42:13,916 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 30.0) internal successors, (90), 3 states have internal predecessors, (90), 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) [2021-11-06 14:42:13,916 INFO L276 IsEmpty]: Start isEmpty. Operand 51893 states and 72585 transitions. [2021-11-06 14:42:13,923 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2021-11-06 14:42:13,923 INFO L505 BasicCegarLoop]: Found error trace [2021-11-06 14:42:13,923 INFO L513 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-06 14:42:13,950 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2021-11-06 14:42:14,139 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-06 14:42:14,140 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-06 14:42:14,140 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-06 14:42:14,140 INFO L85 PathProgramCache]: Analyzing trace with hash 339258647, now seen corresponding path program 1 times [2021-11-06 14:42:14,140 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-11-06 14:42:14,140 INFO L332 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [999245] [2021-11-06 14:42:14,140 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-06 14:42:14,140 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-06 14:42:14,385 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-06 14:42:15,054 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 3 proven. 8 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-06 14:42:15,055 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-11-06 14:42:15,055 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [999245] [2021-11-06 14:42:15,055 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [999245] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-06 14:42:15,055 INFO L332 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1315050643] [2021-11-06 14:42:15,055 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-06 14:42:15,055 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-06 14:42:15,055 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-11-06 14:42:15,056 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-06 14:42:15,083 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-11-06 14:42:16,056 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-06 14:42:16,067 INFO L263 TraceCheckSpWp]: Trace formula consists of 2501 conjuncts, 19 conjunts are in the unsatisfiable core [2021-11-06 14:42:16,072 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-06 14:42:16,444 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-11-06 14:42:16,445 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1315050643] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-06 14:42:16,445 INFO L186 FreeRefinementEngine]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2021-11-06 14:42:16,445 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [13] total 17 [2021-11-06 14:42:16,445 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1529731406] [2021-11-06 14:42:16,445 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-11-06 14:42:16,445 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-11-06 14:42:16,446 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-11-06 14:42:16,446 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=231, Unknown=0, NotChecked=0, Total=272 [2021-11-06 14:42:16,446 INFO L87 Difference]: Start difference. First operand 51893 states and 72585 transitions. Second operand has 5 states, 5 states have (on average 18.4) internal successors, (92), 5 states have internal predecessors, (92), 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) [2021-11-06 14:42:20,348 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-06 14:42:20,348 INFO L93 Difference]: Finished difference Result 103511 states and 144792 transitions. [2021-11-06 14:42:20,349 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-11-06 14:42:20,349 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 18.4) internal successors, (92), 5 states have internal predecessors, (92), 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 94 [2021-11-06 14:42:20,349 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-06 14:42:20,487 INFO L225 Difference]: With dead ends: 103511 [2021-11-06 14:42:20,488 INFO L226 Difference]: Without dead ends: 51891 [2021-11-06 14:42:20,580 INFO L786 BasicCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 94 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=51, Invalid=291, Unknown=0, NotChecked=0, Total=342 [2021-11-06 14:42:20,619 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51891 states.