/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound5.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-b030c9e [2022-03-20 06:19:46,003 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-20 06:19:46,005 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-20 06:19:46,049 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-20 06:19:46,050 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-20 06:19:46,053 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-20 06:19:46,055 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-20 06:19:46,060 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-20 06:19:46,061 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-20 06:19:46,063 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-20 06:19:46,066 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-20 06:19:46,066 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-20 06:19:46,067 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-20 06:19:46,067 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-20 06:19:46,068 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-20 06:19:46,069 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-20 06:19:46,070 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-20 06:19:46,070 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-20 06:19:46,072 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-20 06:19:46,075 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-20 06:19:46,077 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-20 06:19:46,080 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-20 06:19:46,080 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-20 06:19:46,081 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-20 06:19:46,082 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-20 06:19:46,084 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-20 06:19:46,084 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-20 06:19:46,085 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-20 06:19:46,085 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-20 06:19:46,086 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-20 06:19:46,086 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-20 06:19:46,087 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-20 06:19:46,087 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-20 06:19:46,088 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-20 06:19:46,088 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-20 06:19:46,089 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-20 06:19:46,089 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-20 06:19:46,090 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-20 06:19:46,090 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-20 06:19:46,090 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-20 06:19:46,099 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-20 06:19:46,102 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-20 06:19:46,103 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-03-20 06:19:46,113 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-20 06:19:46,114 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-20 06:19:46,115 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-20 06:19:46,115 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-20 06:19:46,115 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-20 06:19:46,115 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-20 06:19:46,116 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-20 06:19:46,116 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-20 06:19:46,116 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-20 06:19:46,117 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-20 06:19:46,117 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-20 06:19:46,117 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-20 06:19:46,117 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-20 06:19:46,117 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-20 06:19:46,117 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-20 06:19:46,117 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-20 06:19:46,117 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-20 06:19:46,118 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-20 06:19:46,118 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 06:19:46,118 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-20 06:19:46,118 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-20 06:19:46,119 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-20 06:19:46,120 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_JORDAN 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.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-03-20 06:19:46,330 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-20 06:19:46,357 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-20 06:19:46,359 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-20 06:19:46,360 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-20 06:19:46,361 INFO L275 PluginConnector]: CDTParser initialized [2022-03-20 06:19:46,362 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound5.c [2022-03-20 06:19:46,431 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e44e1f87e/f6ab87ecaadb47b48ee1e84e761d4b00/FLAG2410508fd [2022-03-20 06:19:46,858 INFO L306 CDTParser]: Found 1 translation units. [2022-03-20 06:19:46,859 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound5.c [2022-03-20 06:19:46,867 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e44e1f87e/f6ab87ecaadb47b48ee1e84e761d4b00/FLAG2410508fd [2022-03-20 06:19:46,886 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e44e1f87e/f6ab87ecaadb47b48ee1e84e761d4b00 [2022-03-20 06:19:46,889 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-20 06:19:46,891 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-20 06:19:46,898 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-20 06:19:46,898 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-20 06:19:46,902 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-20 06:19:46,903 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 06:19:46" (1/1) ... [2022-03-20 06:19:46,904 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7282735e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 06:19:46, skipping insertion in model container [2022-03-20 06:19:46,904 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 06:19:46" (1/1) ... [2022-03-20 06:19:46,911 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-20 06:19:46,927 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-20 06:19:47,100 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound5.c[526,539] [2022-03-20 06:19:47,112 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 06:19:47,124 INFO L203 MainTranslator]: Completed pre-run [2022-03-20 06:19:47,137 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound5.c[526,539] [2022-03-20 06:19:47,162 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 06:19:47,175 INFO L208 MainTranslator]: Completed translation [2022-03-20 06:19:47,176 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 06:19:47 WrapperNode [2022-03-20 06:19:47,176 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-20 06:19:47,177 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-20 06:19:47,177 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-20 06:19:47,178 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-20 06:19:47,195 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 06:19:47" (1/1) ... [2022-03-20 06:19:47,195 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 06:19:47" (1/1) ... [2022-03-20 06:19:47,201 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 06:19:47" (1/1) ... [2022-03-20 06:19:47,201 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 06:19:47" (1/1) ... [2022-03-20 06:19:47,213 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 06:19:47" (1/1) ... [2022-03-20 06:19:47,219 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 06:19:47" (1/1) ... [2022-03-20 06:19:47,228 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 06:19:47" (1/1) ... [2022-03-20 06:19:47,230 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-20 06:19:47,231 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-20 06:19:47,231 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-20 06:19:47,231 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-20 06:19:47,233 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 06:19:47" (1/1) ... [2022-03-20 06:19:47,239 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 06:19:47,248 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 06:19:47,259 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) [2022-03-20 06:19:47,293 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 [2022-03-20 06:19:47,312 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-20 06:19:47,312 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-20 06:19:47,313 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-20 06:19:47,313 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-20 06:19:47,314 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-20 06:19:47,314 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-20 06:19:47,314 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-20 06:19:47,314 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-20 06:19:47,314 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-20 06:19:47,315 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-20 06:19:47,315 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-03-20 06:19:47,315 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-20 06:19:47,316 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-20 06:19:47,316 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-20 06:19:47,317 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-20 06:19:47,317 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-20 06:19:47,317 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-20 06:19:47,318 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-20 06:19:47,318 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-20 06:19:47,318 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-20 06:19:47,397 INFO L234 CfgBuilder]: Building ICFG [2022-03-20 06:19:47,398 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-20 06:19:47,604 INFO L275 CfgBuilder]: Performing block encoding [2022-03-20 06:19:47,611 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-20 06:19:47,611 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-20 06:19:47,613 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 06:19:47 BoogieIcfgContainer [2022-03-20 06:19:47,613 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-20 06:19:47,614 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-20 06:19:47,614 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-20 06:19:47,634 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-20 06:19:47,649 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 06:19:47" (1/1) ... [2022-03-20 06:19:47,651 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_JORDAN [2022-03-20 06:19:47,683 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 20.03 06:19:47 BasicIcfg [2022-03-20 06:19:47,683 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-20 06:19:47,685 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-20 06:19:47,685 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-20 06:19:47,688 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-20 06:19:47,688 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.03 06:19:46" (1/4) ... [2022-03-20 06:19:47,689 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@61e67f3e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 06:19:47, skipping insertion in model container [2022-03-20 06:19:47,689 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 06:19:47" (2/4) ... [2022-03-20 06:19:47,689 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@61e67f3e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 06:19:47, skipping insertion in model container [2022-03-20 06:19:47,689 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 06:19:47" (3/4) ... [2022-03-20 06:19:47,690 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@61e67f3e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.03 06:19:47, skipping insertion in model container [2022-03-20 06:19:47,690 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 20.03 06:19:47" (4/4) ... [2022-03-20 06:19:47,691 INFO L111 eAbstractionObserver]: Analyzing ICFG hard2_unwindbound5.cJordan [2022-03-20 06:19:47,711 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-03-20 06:19:47,711 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-20 06:19:47,780 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-20 06:19:47,791 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=ForwardPredicates, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, 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 [2022-03-20 06:19:47,791 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-20 06:19:47,803 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-20 06:19:47,810 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-03-20 06:19:47,811 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:19:47,811 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:19:47,812 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:19:47,819 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:19:47,819 INFO L85 PathProgramCache]: Analyzing trace with hash 121155216, now seen corresponding path program 1 times [2022-03-20 06:19:47,827 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:19:47,828 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [619439374] [2022-03-20 06:19:47,828 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:47,829 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:19:47,914 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:47,986 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 06:19:47,991 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:48,000 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 06:19:48,000 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:19:48,001 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [619439374] [2022-03-20 06:19:48,001 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [619439374] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 06:19:48,001 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 06:19:48,002 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 06:19:48,003 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [590000086] [2022-03-20 06:19:48,003 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 06:19:48,008 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-20 06:19:48,008 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:19:48,030 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-20 06:19:48,031 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 06:19:48,033 INFO L87 Difference]: Start difference. First operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-20 06:19:48,113 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:19:48,114 INFO L93 Difference]: Finished difference Result 32 states and 42 transitions. [2022-03-20 06:19:48,128 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-20 06:19:48,130 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-03-20 06:19:48,130 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:19:48,144 INFO L225 Difference]: With dead ends: 32 [2022-03-20 06:19:48,145 INFO L226 Difference]: Without dead ends: 27 [2022-03-20 06:19:48,146 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 06:19:48,151 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 06:19:48,152 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 44 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 06:19:48,170 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-03-20 06:19:48,193 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2022-03-20 06:19:48,195 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-20 06:19:48,198 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 36 transitions. [2022-03-20 06:19:48,199 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 36 transitions. Word has length 12 [2022-03-20 06:19:48,200 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:19:48,200 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 36 transitions. [2022-03-20 06:19:48,201 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-20 06:19:48,201 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 36 transitions. [2022-03-20 06:19:48,202 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-03-20 06:19:48,202 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:19:48,202 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:19:48,203 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-20 06:19:48,203 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:19:48,206 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:19:48,206 INFO L85 PathProgramCache]: Analyzing trace with hash 152644303, now seen corresponding path program 1 times [2022-03-20 06:19:48,207 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:19:48,207 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1280905384] [2022-03-20 06:19:48,207 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:48,207 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:19:48,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:48,271 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 06:19:48,273 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:48,285 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 06:19:48,285 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:19:48,285 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1280905384] [2022-03-20 06:19:48,285 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1280905384] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 06:19:48,286 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 06:19:48,286 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 06:19:48,286 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1666093125] [2022-03-20 06:19:48,286 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 06:19:48,287 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 06:19:48,287 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:19:48,288 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 06:19:48,288 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-20 06:19:48,288 INFO L87 Difference]: Start difference. First operand 26 states and 36 transitions. Second operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-20 06:19:48,443 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:19:48,443 INFO L93 Difference]: Finished difference Result 39 states and 54 transitions. [2022-03-20 06:19:48,444 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-20 06:19:48,444 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-03-20 06:19:48,444 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:19:48,446 INFO L225 Difference]: With dead ends: 39 [2022-03-20 06:19:48,447 INFO L226 Difference]: Without dead ends: 39 [2022-03-20 06:19:48,447 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-20 06:19:48,448 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 24 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 87 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 06:19:48,449 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 91 Invalid, 87 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 06:19:48,449 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-03-20 06:19:48,454 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 30. [2022-03-20 06:19:48,454 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-20 06:19:48,455 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2022-03-20 06:19:48,455 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 12 [2022-03-20 06:19:48,455 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:19:48,455 INFO L478 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2022-03-20 06:19:48,455 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-20 06:19:48,456 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2022-03-20 06:19:48,456 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-03-20 06:19:48,456 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:19:48,456 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:19:48,456 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-20 06:19:48,456 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:19:48,457 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:19:48,457 INFO L85 PathProgramCache]: Analyzing trace with hash -400958603, now seen corresponding path program 1 times [2022-03-20 06:19:48,457 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:19:48,457 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [946135632] [2022-03-20 06:19:48,457 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:48,458 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:19:48,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:48,491 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 06:19:48,495 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:48,501 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 06:19:48,502 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:19:48,502 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [946135632] [2022-03-20 06:19:48,502 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [946135632] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 06:19:48,502 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 06:19:48,502 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-03-20 06:19:48,502 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1474292171] [2022-03-20 06:19:48,502 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 06:19:48,503 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 06:19:48,503 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:19:48,503 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 06:19:48,503 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 06:19:48,504 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-20 06:19:48,571 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:19:48,572 INFO L93 Difference]: Finished difference Result 32 states and 41 transitions. [2022-03-20 06:19:48,572 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-20 06:19:48,572 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2022-03-20 06:19:48,572 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:19:48,573 INFO L225 Difference]: With dead ends: 32 [2022-03-20 06:19:48,573 INFO L226 Difference]: Without dead ends: 32 [2022-03-20 06:19:48,574 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-20 06:19:48,575 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 39 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 06:19:48,575 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 73 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 06:19:48,575 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-03-20 06:19:48,578 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-03-20 06:19:48,578 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-20 06:19:48,579 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2022-03-20 06:19:48,579 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 14 [2022-03-20 06:19:48,579 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:19:48,579 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2022-03-20 06:19:48,579 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-20 06:19:48,580 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-03-20 06:19:48,580 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-20 06:19:48,580 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:19:48,580 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:19:48,580 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-03-20 06:19:48,580 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:19:48,581 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:19:48,581 INFO L85 PathProgramCache]: Analyzing trace with hash 185978583, now seen corresponding path program 1 times [2022-03-20 06:19:48,581 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:19:48,581 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [44652299] [2022-03-20 06:19:48,581 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:48,581 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:19:48,590 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:48,621 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 06:19:48,624 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:48,627 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2022-03-20 06:19:48,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:48,633 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 06:19:48,633 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:19:48,633 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [44652299] [2022-03-20 06:19:48,634 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [44652299] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 06:19:48,634 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 06:19:48,634 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 06:19:48,634 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [490295017] [2022-03-20 06:19:48,634 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 06:19:48,634 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 06:19:48,635 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:19:48,635 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 06:19:48,635 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-20 06:19:48,635 INFO L87 Difference]: Start difference. First operand 32 states and 41 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-20 06:19:48,741 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:19:48,741 INFO L93 Difference]: Finished difference Result 44 states and 58 transitions. [2022-03-20 06:19:48,741 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-20 06:19:48,742 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2022-03-20 06:19:48,742 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:19:48,742 INFO L225 Difference]: With dead ends: 44 [2022-03-20 06:19:48,743 INFO L226 Difference]: Without dead ends: 44 [2022-03-20 06:19:48,743 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-20 06:19:48,744 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 19 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 87 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 100 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 87 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 06:19:48,744 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 84 Invalid, 100 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 87 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 06:19:48,745 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-03-20 06:19:48,748 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 36. [2022-03-20 06:19:48,748 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-20 06:19:48,749 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 44 transitions. [2022-03-20 06:19:48,749 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 44 transitions. Word has length 17 [2022-03-20 06:19:48,749 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:19:48,750 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 44 transitions. [2022-03-20 06:19:48,750 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-20 06:19:48,750 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 44 transitions. [2022-03-20 06:19:48,750 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-03-20 06:19:48,750 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:19:48,750 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:19:48,751 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-03-20 06:19:48,751 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:19:48,751 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:19:48,751 INFO L85 PathProgramCache]: Analyzing trace with hash -820589269, now seen corresponding path program 1 times [2022-03-20 06:19:48,751 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:19:48,757 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1421055331] [2022-03-20 06:19:48,757 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:48,757 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:19:48,771 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 06:19:48,772 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1110891976] [2022-03-20 06:19:48,772 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:48,772 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:19:48,772 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 06:19:48,793 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) [2022-03-20 06:19:48,831 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-03-20 06:19:48,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:48,858 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-20 06:19:48,866 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 06:19:49,060 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-20 06:19:49,060 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 06:19:49,062 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:19:49,062 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1421055331] [2022-03-20 06:19:49,062 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 06:19:49,063 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1110891976] [2022-03-20 06:19:49,063 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1110891976] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 06:19:49,063 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 06:19:49,063 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 06:19:49,063 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1518527232] [2022-03-20 06:19:49,063 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 06:19:49,063 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 06:19:49,064 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:19:49,064 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 06:19:49,064 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 06:19:49,064 INFO L87 Difference]: Start difference. First operand 36 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 06:19:49,100 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:19:49,100 INFO L93 Difference]: Finished difference Result 51 states and 66 transitions. [2022-03-20 06:19:49,101 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 06:19:49,101 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-03-20 06:19:49,101 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:19:49,102 INFO L225 Difference]: With dead ends: 51 [2022-03-20 06:19:49,102 INFO L226 Difference]: Without dead ends: 50 [2022-03-20 06:19:49,102 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-20 06:19:49,104 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 10 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 06:19:49,104 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 131 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 06:19:49,105 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-03-20 06:19:49,109 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2022-03-20 06:19:49,109 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-20 06:19:49,110 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 64 transitions. [2022-03-20 06:19:49,110 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 64 transitions. Word has length 22 [2022-03-20 06:19:49,110 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:19:49,111 INFO L478 AbstractCegarLoop]: Abstraction has 50 states and 64 transitions. [2022-03-20 06:19:49,111 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 06:19:49,111 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2022-03-20 06:19:49,111 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-03-20 06:19:49,111 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:19:49,111 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:19:49,131 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-03-20 06:19:49,319 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:19:49,321 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:19:49,322 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:19:49,322 INFO L85 PathProgramCache]: Analyzing trace with hash 1259710898, now seen corresponding path program 1 times [2022-03-20 06:19:49,322 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:19:49,322 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [687926364] [2022-03-20 06:19:49,323 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:49,323 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:19:49,342 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 06:19:49,342 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [95534020] [2022-03-20 06:19:49,342 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:49,342 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:19:49,342 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 06:19:49,348 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) [2022-03-20 06:19:49,349 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-03-20 06:19:49,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:49,401 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 06:19:49,403 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 06:19:49,497 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 06:19:49,498 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 06:19:49,498 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:19:49,498 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [687926364] [2022-03-20 06:19:49,498 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 06:19:49,498 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [95534020] [2022-03-20 06:19:49,498 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [95534020] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 06:19:49,498 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 06:19:49,498 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 06:19:49,498 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [618014544] [2022-03-20 06:19:49,499 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 06:19:49,499 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 06:19:49,499 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:19:49,499 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 06:19:49,499 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-20 06:19:49,500 INFO L87 Difference]: Start difference. First operand 50 states and 64 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 06:19:49,518 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:19:49,518 INFO L93 Difference]: Finished difference Result 63 states and 73 transitions. [2022-03-20 06:19:49,518 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 06:19:49,518 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-03-20 06:19:49,519 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:19:49,519 INFO L225 Difference]: With dead ends: 63 [2022-03-20 06:19:49,519 INFO L226 Difference]: Without dead ends: 63 [2022-03-20 06:19:49,519 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-20 06:19:49,520 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 3 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 06:19:49,520 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 124 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 06:19:49,521 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-03-20 06:19:49,524 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2022-03-20 06:19:49,525 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-20 06:19:49,526 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 72 transitions. [2022-03-20 06:19:49,526 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 72 transitions. Word has length 30 [2022-03-20 06:19:49,526 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:19:49,526 INFO L478 AbstractCegarLoop]: Abstraction has 62 states and 72 transitions. [2022-03-20 06:19:49,526 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 06:19:49,527 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 72 transitions. [2022-03-20 06:19:49,527 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-03-20 06:19:49,527 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:19:49,527 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:19:49,548 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-03-20 06:19:49,745 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2022-03-20 06:19:49,745 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:19:49,746 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:19:49,746 INFO L85 PathProgramCache]: Analyzing trace with hash 1260813165, now seen corresponding path program 1 times [2022-03-20 06:19:49,746 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:19:49,746 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2006645472] [2022-03-20 06:19:49,746 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:49,746 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:19:49,754 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 06:19:49,755 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [643429057] [2022-03-20 06:19:49,755 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:49,755 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:19:49,755 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 06:19:49,758 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 06:19:49,764 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-03-20 06:19:49,822 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:49,824 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 06:19:49,825 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 06:19:49,949 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 06:19:49,949 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 06:19:49,949 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:19:49,949 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2006645472] [2022-03-20 06:19:49,950 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 06:19:49,950 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [643429057] [2022-03-20 06:19:49,950 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [643429057] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 06:19:49,950 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 06:19:49,950 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 06:19:49,950 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1716166925] [2022-03-20 06:19:49,950 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 06:19:49,950 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 06:19:49,951 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:19:49,951 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 06:19:49,951 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 06:19:49,951 INFO L87 Difference]: Start difference. First operand 62 states and 72 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 06:19:50,014 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:19:50,015 INFO L93 Difference]: Finished difference Result 74 states and 89 transitions. [2022-03-20 06:19:50,015 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 06:19:50,015 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-03-20 06:19:50,015 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:19:50,016 INFO L225 Difference]: With dead ends: 74 [2022-03-20 06:19:50,016 INFO L226 Difference]: Without dead ends: 64 [2022-03-20 06:19:50,016 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-20 06:19:50,017 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 11 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 06:19:50,017 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 103 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 06:19:50,018 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2022-03-20 06:19:50,021 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 63. [2022-03-20 06:19:50,022 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-03-20 06:19:50,023 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 76 transitions. [2022-03-20 06:19:50,023 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 76 transitions. Word has length 30 [2022-03-20 06:19:50,023 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:19:50,023 INFO L478 AbstractCegarLoop]: Abstraction has 63 states and 76 transitions. [2022-03-20 06:19:50,023 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 06:19:50,023 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 76 transitions. [2022-03-20 06:19:50,024 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-03-20 06:19:50,024 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:19:50,024 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:19:50,054 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-03-20 06:19:50,242 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:19:50,243 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:19:50,243 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:19:50,243 INFO L85 PathProgramCache]: Analyzing trace with hash 1811137592, now seen corresponding path program 1 times [2022-03-20 06:19:50,244 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:19:50,244 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2118257597] [2022-03-20 06:19:50,244 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:50,244 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:19:50,253 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 06:19:50,253 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [856633125] [2022-03-20 06:19:50,253 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:50,253 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:19:50,254 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 06:19:50,260 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 06:19:50,284 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-03-20 06:19:50,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:50,326 INFO L263 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 06:19:50,328 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 06:19:50,428 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 18 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-03-20 06:19:50,428 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 06:19:50,533 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-20 06:19:50,533 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:19:50,534 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2118257597] [2022-03-20 06:19:50,534 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 06:19:50,534 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [856633125] [2022-03-20 06:19:50,534 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [856633125] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 06:19:50,534 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 06:19:50,534 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-03-20 06:19:50,534 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [84729202] [2022-03-20 06:19:50,534 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 06:19:50,535 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-20 06:19:50,535 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:19:50,535 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-20 06:19:50,535 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-03-20 06:19:50,535 INFO L87 Difference]: Start difference. First operand 63 states and 76 transitions. Second operand has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 6 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) [2022-03-20 06:19:50,596 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:19:50,596 INFO L93 Difference]: Finished difference Result 119 states and 139 transitions. [2022-03-20 06:19:50,596 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 06:19:50,596 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 6 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) Word has length 37 [2022-03-20 06:19:50,597 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:19:50,612 INFO L225 Difference]: With dead ends: 119 [2022-03-20 06:19:50,612 INFO L226 Difference]: Without dead ends: 119 [2022-03-20 06:19:50,613 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2022-03-20 06:19:50,613 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 41 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 152 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 06:19:50,613 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 152 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 06:19:50,614 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2022-03-20 06:19:50,620 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 112. [2022-03-20 06:19:50,621 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 112 states, 71 states have (on average 1.2112676056338028) internal successors, (86), 74 states have internal predecessors, (86), 25 states have call successors, (25), 16 states have call predecessors, (25), 15 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2022-03-20 06:19:50,622 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 133 transitions. [2022-03-20 06:19:50,622 INFO L78 Accepts]: Start accepts. Automaton has 112 states and 133 transitions. Word has length 37 [2022-03-20 06:19:50,622 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:19:50,622 INFO L478 AbstractCegarLoop]: Abstraction has 112 states and 133 transitions. [2022-03-20 06:19:50,623 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 6 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) [2022-03-20 06:19:50,623 INFO L276 IsEmpty]: Start isEmpty. Operand 112 states and 133 transitions. [2022-03-20 06:19:50,623 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-03-20 06:19:50,623 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:19:50,623 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:19:50,645 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-03-20 06:19:50,837 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:19:50,838 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:19:50,838 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:19:50,838 INFO L85 PathProgramCache]: Analyzing trace with hash -599722260, now seen corresponding path program 1 times [2022-03-20 06:19:50,838 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:19:50,838 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1674956874] [2022-03-20 06:19:50,838 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:50,839 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:19:50,845 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 06:19:50,845 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1331526386] [2022-03-20 06:19:50,845 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:50,845 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:19:50,845 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 06:19:50,852 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 06:19:50,872 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-03-20 06:19:50,916 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:50,918 INFO L263 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-20 06:19:50,919 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 06:19:51,046 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-03-20 06:19:51,046 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 06:19:51,122 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-03-20 06:19:51,122 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:19:51,122 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1674956874] [2022-03-20 06:19:51,122 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 06:19:51,122 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1331526386] [2022-03-20 06:19:51,122 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1331526386] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 06:19:51,122 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 06:19:51,122 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-03-20 06:19:51,123 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [276464287] [2022-03-20 06:19:51,123 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 06:19:51,123 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 06:19:51,123 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:19:51,123 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 06:19:51,123 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-20 06:19:51,124 INFO L87 Difference]: Start difference. First operand 112 states and 133 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 06:19:51,152 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:19:51,152 INFO L93 Difference]: Finished difference Result 127 states and 150 transitions. [2022-03-20 06:19:51,152 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 06:19:51,152 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 40 [2022-03-20 06:19:51,152 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:19:51,153 INFO L225 Difference]: With dead ends: 127 [2022-03-20 06:19:51,153 INFO L226 Difference]: Without dead ends: 125 [2022-03-20 06:19:51,153 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 72 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-03-20 06:19:51,154 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 11 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 06:19:51,154 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 113 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 06:19:51,154 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2022-03-20 06:19:51,160 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 122. [2022-03-20 06:19:51,160 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 78 states have (on average 1.1794871794871795) internal successors, (92), 81 states have internal predecessors, (92), 27 states have call successors, (27), 18 states have call predecessors, (27), 16 states have return successors, (24), 22 states have call predecessors, (24), 24 states have call successors, (24) [2022-03-20 06:19:51,161 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 143 transitions. [2022-03-20 06:19:51,161 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 143 transitions. Word has length 40 [2022-03-20 06:19:51,161 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:19:51,161 INFO L478 AbstractCegarLoop]: Abstraction has 122 states and 143 transitions. [2022-03-20 06:19:51,161 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 06:19:51,161 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 143 transitions. [2022-03-20 06:19:51,162 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2022-03-20 06:19:51,162 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:19:51,162 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:19:51,181 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-03-20 06:19:51,379 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:19:51,379 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:19:51,380 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:19:51,380 INFO L85 PathProgramCache]: Analyzing trace with hash 560903707, now seen corresponding path program 1 times [2022-03-20 06:19:51,380 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:19:51,380 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [361329770] [2022-03-20 06:19:51,380 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:51,380 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:19:51,389 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 06:19:51,389 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [475511565] [2022-03-20 06:19:51,389 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:51,389 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:19:51,389 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 06:19:51,390 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 06:19:51,391 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-03-20 06:19:51,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:51,427 INFO L263 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-20 06:19:51,429 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 06:19:51,515 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 36 proven. 42 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2022-03-20 06:19:51,516 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 06:19:51,617 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-03-20 06:19:51,617 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:19:51,617 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [361329770] [2022-03-20 06:19:51,617 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 06:19:51,617 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [475511565] [2022-03-20 06:19:51,617 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [475511565] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 06:19:51,617 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 06:19:51,618 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-03-20 06:19:51,618 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [5004141] [2022-03-20 06:19:51,618 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 06:19:51,618 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 06:19:51,618 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:19:51,618 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 06:19:51,618 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2022-03-20 06:19:51,619 INFO L87 Difference]: Start difference. First operand 122 states and 143 transitions. Second operand has 9 states, 9 states have (on average 4.0) internal successors, (36), 9 states have internal predecessors, (36), 7 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2022-03-20 06:19:51,696 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:19:51,697 INFO L93 Difference]: Finished difference Result 177 states and 208 transitions. [2022-03-20 06:19:51,697 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 06:19:51,697 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.0) internal successors, (36), 9 states have internal predecessors, (36), 7 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 53 [2022-03-20 06:19:51,697 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:19:51,698 INFO L225 Difference]: With dead ends: 177 [2022-03-20 06:19:51,698 INFO L226 Difference]: Without dead ends: 177 [2022-03-20 06:19:51,698 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 97 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=37, Invalid=73, Unknown=0, NotChecked=0, Total=110 [2022-03-20 06:19:51,699 INFO L913 BasicCegarLoop]: 54 mSDtfsCounter, 52 mSDsluCounter, 149 mSDsCounter, 0 mSdLazyCounter, 75 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 203 SdHoareTripleChecker+Invalid, 88 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 75 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 06:19:51,699 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [52 Valid, 203 Invalid, 88 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 75 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 06:19:51,700 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2022-03-20 06:19:51,706 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 172. [2022-03-20 06:19:51,707 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 172 states, 111 states have (on average 1.1801801801801801) internal successors, (131), 117 states have internal predecessors, (131), 39 states have call successors, (39), 23 states have call predecessors, (39), 21 states have return successors, (35), 31 states have call predecessors, (35), 35 states have call successors, (35) [2022-03-20 06:19:51,708 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 172 states to 172 states and 205 transitions. [2022-03-20 06:19:51,708 INFO L78 Accepts]: Start accepts. Automaton has 172 states and 205 transitions. Word has length 53 [2022-03-20 06:19:51,708 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:19:51,708 INFO L478 AbstractCegarLoop]: Abstraction has 172 states and 205 transitions. [2022-03-20 06:19:51,708 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.0) internal successors, (36), 9 states have internal predecessors, (36), 7 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2022-03-20 06:19:51,708 INFO L276 IsEmpty]: Start isEmpty. Operand 172 states and 205 transitions. [2022-03-20 06:19:51,709 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2022-03-20 06:19:51,709 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:19:51,710 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:19:51,730 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-20 06:19:51,923 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:19:51,923 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:19:51,923 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:19:51,924 INFO L85 PathProgramCache]: Analyzing trace with hash -453219492, now seen corresponding path program 1 times [2022-03-20 06:19:51,924 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:19:51,924 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1219876994] [2022-03-20 06:19:51,924 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:51,924 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:19:51,930 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 06:19:51,930 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1317463835] [2022-03-20 06:19:51,930 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:51,930 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:19:51,931 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 06:19:51,948 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 06:19:51,975 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-03-20 06:19:52,013 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:52,014 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 25 conjunts are in the unsatisfiable core [2022-03-20 06:19:52,020 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 06:19:52,328 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-03-20 06:19:52,328 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 06:19:53,154 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-03-20 06:19:53,154 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:19:53,155 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1219876994] [2022-03-20 06:19:53,155 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 06:19:53,155 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1317463835] [2022-03-20 06:19:53,155 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1317463835] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 06:19:53,155 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 06:19:53,155 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-03-20 06:19:53,155 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [90858270] [2022-03-20 06:19:53,155 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 06:19:53,155 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-20 06:19:53,156 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:19:53,156 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-20 06:19:53,156 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-03-20 06:19:53,156 INFO L87 Difference]: Start difference. First operand 172 states and 205 transitions. Second operand has 10 states, 10 states have (on average 3.4) internal successors, (34), 9 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2022-03-20 06:19:57,752 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:19:57,753 INFO L93 Difference]: Finished difference Result 232 states and 291 transitions. [2022-03-20 06:19:57,753 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 06:19:57,753 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 9 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) Word has length 62 [2022-03-20 06:19:57,754 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:19:57,755 INFO L225 Difference]: With dead ends: 232 [2022-03-20 06:19:57,755 INFO L226 Difference]: Without dead ends: 225 [2022-03-20 06:19:57,755 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 112 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=50, Invalid=132, Unknown=0, NotChecked=0, Total=182 [2022-03-20 06:19:57,756 INFO L913 BasicCegarLoop]: 50 mSDtfsCounter, 52 mSDsluCounter, 211 mSDsCounter, 0 mSdLazyCounter, 217 mSolverCounterSat, 74 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 261 SdHoareTripleChecker+Invalid, 291 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 74 IncrementalHoareTripleChecker+Valid, 217 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-03-20 06:19:57,756 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [58 Valid, 261 Invalid, 291 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [74 Valid, 217 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2022-03-20 06:19:57,756 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 225 states. [2022-03-20 06:19:57,773 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 225 to 212. [2022-03-20 06:19:57,774 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 212 states, 141 states have (on average 1.2198581560283688) internal successors, (172), 147 states have internal predecessors, (172), 45 states have call successors, (45), 26 states have call predecessors, (45), 25 states have return successors, (42), 38 states have call predecessors, (42), 42 states have call successors, (42) [2022-03-20 06:19:57,782 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 212 states to 212 states and 259 transitions. [2022-03-20 06:19:57,783 INFO L78 Accepts]: Start accepts. Automaton has 212 states and 259 transitions. Word has length 62 [2022-03-20 06:19:57,783 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:19:57,783 INFO L478 AbstractCegarLoop]: Abstraction has 212 states and 259 transitions. [2022-03-20 06:19:57,783 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 9 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2022-03-20 06:19:57,784 INFO L276 IsEmpty]: Start isEmpty. Operand 212 states and 259 transitions. [2022-03-20 06:19:57,785 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2022-03-20 06:19:57,785 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:19:57,785 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:19:57,835 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-03-20 06:19:58,007 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:19:58,008 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:19:58,008 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:19:58,009 INFO L85 PathProgramCache]: Analyzing trace with hash 929445032, now seen corresponding path program 1 times [2022-03-20 06:19:58,009 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:19:58,009 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2084032909] [2022-03-20 06:19:58,009 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:58,009 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:19:58,017 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 06:19:58,018 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [397914679] [2022-03-20 06:19:58,018 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:58,018 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:19:58,018 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 06:19:58,044 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 06:19:58,046 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-03-20 06:19:58,092 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:58,093 INFO L263 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 35 conjunts are in the unsatisfiable core [2022-03-20 06:19:58,096 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 06:19:58,676 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 66 proven. 13 refuted. 0 times theorem prover too weak. 132 trivial. 0 not checked. [2022-03-20 06:19:58,676 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 06:19:59,036 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 68 proven. 2 refuted. 0 times theorem prover too weak. 141 trivial. 0 not checked. [2022-03-20 06:19:59,036 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:19:59,036 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2084032909] [2022-03-20 06:19:59,037 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 06:19:59,037 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [397914679] [2022-03-20 06:19:59,037 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [397914679] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 06:19:59,037 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 06:19:59,037 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 16 [2022-03-20 06:19:59,037 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1002136571] [2022-03-20 06:19:59,037 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 06:19:59,038 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-03-20 06:19:59,038 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:19:59,038 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-03-20 06:19:59,038 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=189, Unknown=0, NotChecked=0, Total=240 [2022-03-20 06:19:59,039 INFO L87 Difference]: Start difference. First operand 212 states and 259 transitions. Second operand has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2022-03-20 06:19:59,502 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:19:59,503 INFO L93 Difference]: Finished difference Result 215 states and 249 transitions. [2022-03-20 06:19:59,503 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-20 06:19:59,503 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) Word has length 73 [2022-03-20 06:19:59,504 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:19:59,505 INFO L225 Difference]: With dead ends: 215 [2022-03-20 06:19:59,505 INFO L226 Difference]: Without dead ends: 184 [2022-03-20 06:19:59,506 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 129 SyntacticMatches, 2 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=76, Invalid=304, Unknown=0, NotChecked=0, Total=380 [2022-03-20 06:19:59,506 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 41 mSDsluCounter, 227 mSDsCounter, 0 mSdLazyCounter, 326 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 261 SdHoareTripleChecker+Invalid, 379 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 326 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-03-20 06:19:59,506 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [54 Valid, 261 Invalid, 379 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 326 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-03-20 06:19:59,507 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2022-03-20 06:19:59,515 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 173. [2022-03-20 06:19:59,518 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 173 states, 114 states have (on average 1.1842105263157894) internal successors, (135), 118 states have internal predecessors, (135), 36 states have call successors, (36), 24 states have call predecessors, (36), 22 states have return successors, (33), 30 states have call predecessors, (33), 33 states have call successors, (33) [2022-03-20 06:19:59,519 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 173 states to 173 states and 204 transitions. [2022-03-20 06:19:59,519 INFO L78 Accepts]: Start accepts. Automaton has 173 states and 204 transitions. Word has length 73 [2022-03-20 06:19:59,520 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:19:59,520 INFO L478 AbstractCegarLoop]: Abstraction has 173 states and 204 transitions. [2022-03-20 06:19:59,520 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2022-03-20 06:19:59,520 INFO L276 IsEmpty]: Start isEmpty. Operand 173 states and 204 transitions. [2022-03-20 06:19:59,521 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2022-03-20 06:19:59,521 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:19:59,521 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:19:59,549 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-03-20 06:19:59,747 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-03-20 06:19:59,748 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:19:59,749 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:19:59,749 INFO L85 PathProgramCache]: Analyzing trace with hash -1139963303, now seen corresponding path program 1 times [2022-03-20 06:19:59,749 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:19:59,749 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [430681930] [2022-03-20 06:19:59,749 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:59,749 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:19:59,762 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 06:19:59,763 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [149306272] [2022-03-20 06:19:59,763 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:19:59,763 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:19:59,763 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 06:19:59,764 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 06:19:59,766 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-03-20 06:19:59,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:19:59,846 INFO L263 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 4 conjunts are in the unsatisfiable core [2022-03-20 06:19:59,850 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 06:20:00,081 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 84 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2022-03-20 06:20:00,081 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 06:20:00,081 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:20:00,082 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [430681930] [2022-03-20 06:20:00,082 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 06:20:00,082 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [149306272] [2022-03-20 06:20:00,082 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [149306272] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 06:20:00,082 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 06:20:00,082 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 06:20:00,082 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1978108176] [2022-03-20 06:20:00,082 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 06:20:00,083 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 06:20:00,083 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:20:00,084 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 06:20:00,084 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-03-20 06:20:00,084 INFO L87 Difference]: Start difference. First operand 173 states and 204 transitions. Second operand has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-03-20 06:20:00,131 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:20:00,131 INFO L93 Difference]: Finished difference Result 172 states and 204 transitions. [2022-03-20 06:20:00,131 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 06:20:00,132 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 82 [2022-03-20 06:20:00,133 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:20:00,135 INFO L225 Difference]: With dead ends: 172 [2022-03-20 06:20:00,135 INFO L226 Difference]: Without dead ends: 172 [2022-03-20 06:20:00,135 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-03-20 06:20:00,137 INFO L913 BasicCegarLoop]: 54 mSDtfsCounter, 27 mSDsluCounter, 35 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 06:20:00,137 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 89 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 06:20:00,138 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 172 states. [2022-03-20 06:20:00,152 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 172 to 167. [2022-03-20 06:20:00,152 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 167 states, 111 states have (on average 1.1711711711711712) internal successors, (130), 113 states have internal predecessors, (130), 34 states have call successors, (34), 22 states have call predecessors, (34), 21 states have return successors, (32), 31 states have call predecessors, (32), 32 states have call successors, (32) [2022-03-20 06:20:00,155 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 167 states to 167 states and 196 transitions. [2022-03-20 06:20:00,156 INFO L78 Accepts]: Start accepts. Automaton has 167 states and 196 transitions. Word has length 82 [2022-03-20 06:20:00,158 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:20:00,158 INFO L478 AbstractCegarLoop]: Abstraction has 167 states and 196 transitions. [2022-03-20 06:20:00,158 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-03-20 06:20:00,158 INFO L276 IsEmpty]: Start isEmpty. Operand 167 states and 196 transitions. [2022-03-20 06:20:00,161 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-03-20 06:20:00,161 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:20:00,161 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 5, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:20:00,189 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2022-03-20 06:20:00,383 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-03-20 06:20:00,384 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:20:00,384 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:20:00,384 INFO L85 PathProgramCache]: Analyzing trace with hash -468178091, now seen corresponding path program 2 times [2022-03-20 06:20:00,384 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:20:00,384 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [88188742] [2022-03-20 06:20:00,384 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:20:00,385 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:20:00,394 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 06:20:00,395 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [512055168] [2022-03-20 06:20:00,395 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 06:20:00,395 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:20:00,395 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 06:20:00,397 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 06:20:00,398 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-03-20 06:20:00,447 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 06:20:00,447 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 06:20:00,449 INFO L263 TraceCheckSpWp]: Trace formula consists of 237 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-20 06:20:00,451 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 06:20:00,655 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 72 proven. 260 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2022-03-20 06:20:00,656 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 06:20:00,819 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 26 proven. 44 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-03-20 06:20:00,819 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:20:00,819 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [88188742] [2022-03-20 06:20:00,819 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 06:20:00,819 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [512055168] [2022-03-20 06:20:00,819 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [512055168] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 06:20:00,819 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 06:20:00,820 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2022-03-20 06:20:00,820 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1676956154] [2022-03-20 06:20:00,820 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 06:20:00,820 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-20 06:20:00,820 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:20:00,820 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-20 06:20:00,820 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2022-03-20 06:20:00,821 INFO L87 Difference]: Start difference. First operand 167 states and 196 transitions. Second operand has 8 states, 8 states have (on average 4.875) internal successors, (39), 8 states have internal predecessors, (39), 7 states have call successors, (29), 7 states have call predecessors, (29), 7 states have return successors, (27), 6 states have call predecessors, (27), 6 states have call successors, (27) [2022-03-20 06:20:00,895 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:20:00,895 INFO L93 Difference]: Finished difference Result 169 states and 198 transitions. [2022-03-20 06:20:00,896 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-20 06:20:00,896 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.875) internal successors, (39), 8 states have internal predecessors, (39), 7 states have call successors, (29), 7 states have call predecessors, (29), 7 states have return successors, (27), 6 states have call predecessors, (27), 6 states have call successors, (27) Word has length 91 [2022-03-20 06:20:00,896 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:20:00,897 INFO L225 Difference]: With dead ends: 169 [2022-03-20 06:20:00,897 INFO L226 Difference]: Without dead ends: 169 [2022-03-20 06:20:00,897 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 185 GetRequests, 174 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=51, Invalid=81, Unknown=0, NotChecked=0, Total=132 [2022-03-20 06:20:00,897 INFO L913 BasicCegarLoop]: 47 mSDtfsCounter, 12 mSDsluCounter, 148 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 195 SdHoareTripleChecker+Invalid, 76 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 06:20:00,898 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 195 Invalid, 76 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 06:20:00,898 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2022-03-20 06:20:00,901 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 169. [2022-03-20 06:20:00,902 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 169 states, 113 states have (on average 1.168141592920354) internal successors, (132), 115 states have internal predecessors, (132), 34 states have call successors, (34), 22 states have call predecessors, (34), 21 states have return successors, (32), 31 states have call predecessors, (32), 32 states have call successors, (32) [2022-03-20 06:20:00,902 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 198 transitions. [2022-03-20 06:20:00,902 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 198 transitions. Word has length 91 [2022-03-20 06:20:00,902 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:20:00,903 INFO L478 AbstractCegarLoop]: Abstraction has 169 states and 198 transitions. [2022-03-20 06:20:00,903 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.875) internal successors, (39), 8 states have internal predecessors, (39), 7 states have call successors, (29), 7 states have call predecessors, (29), 7 states have return successors, (27), 6 states have call predecessors, (27), 6 states have call successors, (27) [2022-03-20 06:20:00,903 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 198 transitions. [2022-03-20 06:20:00,903 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2022-03-20 06:20:00,903 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:20:00,904 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:20:00,924 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-03-20 06:20:01,124 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-03-20 06:20:01,125 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:20:01,125 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:20:01,125 INFO L85 PathProgramCache]: Analyzing trace with hash -2091436208, now seen corresponding path program 1 times [2022-03-20 06:20:01,125 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:20:01,125 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [421929506] [2022-03-20 06:20:01,125 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:20:01,125 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:20:01,132 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 06:20:01,133 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1134931339] [2022-03-20 06:20:01,133 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:20:01,133 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:20:01,133 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 06:20:01,134 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 06:20:01,135 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-03-20 06:20:01,190 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 06:20:01,191 INFO L263 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 39 conjunts are in the unsatisfiable core [2022-03-20 06:20:01,193 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 06:20:01,604 INFO L134 CoverageAnalysis]: Checked inductivity of 366 backedges. 26 proven. 28 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-03-20 06:20:01,605 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 06:20:27,624 INFO L134 CoverageAnalysis]: Checked inductivity of 366 backedges. 26 proven. 28 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-03-20 06:20:27,625 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:20:27,625 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [421929506] [2022-03-20 06:20:27,625 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 06:20:27,625 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1134931339] [2022-03-20 06:20:27,625 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1134931339] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 06:20:27,625 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 06:20:27,625 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2022-03-20 06:20:27,625 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1654290863] [2022-03-20 06:20:27,625 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 06:20:27,626 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-03-20 06:20:27,626 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:20:27,626 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-03-20 06:20:27,626 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=195, Unknown=0, NotChecked=0, Total=240 [2022-03-20 06:20:27,627 INFO L87 Difference]: Start difference. First operand 169 states and 198 transitions. Second operand has 16 states, 16 states have (on average 3.0) internal successors, (48), 15 states have internal predecessors, (48), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) [2022-03-20 06:20:36,623 WARN L232 SmtUtils]: Spent 6.38s on a formula simplification. DAG size of input: 209 DAG size of output: 30 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 06:20:38,927 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 06:20:45,530 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.03s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 06:20:48,475 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.02s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 06:20:48,876 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:20:48,876 INFO L93 Difference]: Finished difference Result 232 states and 293 transitions. [2022-03-20 06:20:48,877 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-03-20 06:20:48,877 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.0) internal successors, (48), 15 states have internal predecessors, (48), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) Word has length 94 [2022-03-20 06:20:48,877 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:20:48,878 INFO L225 Difference]: With dead ends: 232 [2022-03-20 06:20:48,878 INFO L226 Difference]: Without dead ends: 232 [2022-03-20 06:20:48,878 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 192 GetRequests, 171 SyntacticMatches, 3 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 13.4s TimeCoverageRelationStatistics Valid=72, Invalid=308, Unknown=0, NotChecked=0, Total=380 [2022-03-20 06:20:48,879 INFO L913 BasicCegarLoop]: 95 mSDtfsCounter, 74 mSDsluCounter, 741 mSDsCounter, 0 mSdLazyCounter, 507 mSolverCounterSat, 95 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 12.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 87 SdHoareTripleChecker+Valid, 836 SdHoareTripleChecker+Invalid, 604 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 95 IncrementalHoareTripleChecker+Valid, 507 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 12.6s IncrementalHoareTripleChecker+Time [2022-03-20 06:20:48,879 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [87 Valid, 836 Invalid, 604 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [95 Valid, 507 Invalid, 2 Unknown, 0 Unchecked, 12.6s Time] [2022-03-20 06:20:48,880 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 232 states. [2022-03-20 06:20:48,884 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 232 to 198. [2022-03-20 06:20:48,884 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 198 states, 131 states have (on average 1.2061068702290076) internal successors, (158), 135 states have internal predecessors, (158), 44 states have call successors, (44), 23 states have call predecessors, (44), 22 states have return successors, (42), 39 states have call predecessors, (42), 42 states have call successors, (42) [2022-03-20 06:20:48,885 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 198 states to 198 states and 244 transitions. [2022-03-20 06:20:48,885 INFO L78 Accepts]: Start accepts. Automaton has 198 states and 244 transitions. Word has length 94 [2022-03-20 06:20:48,886 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:20:48,886 INFO L478 AbstractCegarLoop]: Abstraction has 198 states and 244 transitions. [2022-03-20 06:20:48,886 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.0) internal successors, (48), 15 states have internal predecessors, (48), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) [2022-03-20 06:20:48,886 INFO L276 IsEmpty]: Start isEmpty. Operand 198 states and 244 transitions. [2022-03-20 06:20:48,886 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2022-03-20 06:20:48,887 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:20:48,887 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:20:48,905 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2022-03-20 06:20:49,087 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2022-03-20 06:20:49,087 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:20:49,088 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:20:49,088 INFO L85 PathProgramCache]: Analyzing trace with hash -2090333941, now seen corresponding path program 2 times [2022-03-20 06:20:49,088 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:20:49,088 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [923319693] [2022-03-20 06:20:49,088 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:20:49,088 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:20:49,094 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 06:20:49,094 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [170814274] [2022-03-20 06:20:49,095 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 06:20:49,095 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:20:49,095 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 06:20:49,102 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 06:20:49,106 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-03-20 06:20:49,154 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 06:20:49,155 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 06:20:49,156 INFO L263 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 15 conjunts are in the unsatisfiable core [2022-03-20 06:20:49,159 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 06:20:49,371 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 322 proven. 2 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2022-03-20 06:20:49,371 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 06:20:49,515 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 54 proven. 2 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-03-20 06:20:49,515 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 06:20:49,515 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [923319693] [2022-03-20 06:20:49,515 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 06:20:49,515 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [170814274] [2022-03-20 06:20:49,515 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [170814274] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 06:20:49,515 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 06:20:49,515 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 9 [2022-03-20 06:20:49,515 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2026985342] [2022-03-20 06:20:49,515 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 06:20:49,516 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 06:20:49,516 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 06:20:49,517 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 06:20:49,517 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=42, Unknown=0, NotChecked=0, Total=72 [2022-03-20 06:20:49,517 INFO L87 Difference]: Start difference. First operand 198 states and 244 transitions. Second operand has 9 states, 9 states have (on average 4.777777777777778) internal successors, (43), 9 states have internal predecessors, (43), 8 states have call successors, (29), 8 states have call predecessors, (29), 7 states have return successors, (27), 6 states have call predecessors, (27), 6 states have call successors, (27) [2022-03-20 06:20:49,591 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 06:20:49,591 INFO L93 Difference]: Finished difference Result 165 states and 177 transitions. [2022-03-20 06:20:49,592 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-20 06:20:49,592 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.777777777777778) internal successors, (43), 9 states have internal predecessors, (43), 8 states have call successors, (29), 8 states have call predecessors, (29), 7 states have return successors, (27), 6 states have call predecessors, (27), 6 states have call successors, (27) Word has length 94 [2022-03-20 06:20:49,592 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 06:20:49,593 INFO L225 Difference]: With dead ends: 165 [2022-03-20 06:20:49,593 INFO L226 Difference]: Without dead ends: 165 [2022-03-20 06:20:49,593 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 188 GetRequests, 179 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=39, Invalid=51, Unknown=0, NotChecked=0, Total=90 [2022-03-20 06:20:49,594 INFO L913 BasicCegarLoop]: 86 mSDtfsCounter, 55 mSDsluCounter, 120 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 206 SdHoareTripleChecker+Invalid, 116 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 06:20:49,594 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [55 Valid, 206 Invalid, 116 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 06:20:49,595 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 165 states. [2022-03-20 06:20:49,597 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 165 to 152. [2022-03-20 06:20:49,598 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 152 states, 102 states have (on average 1.0784313725490196) internal successors, (110), 105 states have internal predecessors, (110), 27 states have call successors, (27), 23 states have call predecessors, (27), 22 states have return successors, (25), 23 states have call predecessors, (25), 25 states have call successors, (25) [2022-03-20 06:20:49,598 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 152 states to 152 states and 162 transitions. [2022-03-20 06:20:49,598 INFO L78 Accepts]: Start accepts. Automaton has 152 states and 162 transitions. Word has length 94 [2022-03-20 06:20:49,599 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 06:20:49,599 INFO L478 AbstractCegarLoop]: Abstraction has 152 states and 162 transitions. [2022-03-20 06:20:49,601 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.777777777777778) internal successors, (43), 9 states have internal predecessors, (43), 8 states have call successors, (29), 8 states have call predecessors, (29), 7 states have return successors, (27), 6 states have call predecessors, (27), 6 states have call successors, (27) [2022-03-20 06:20:49,601 INFO L276 IsEmpty]: Start isEmpty. Operand 152 states and 162 transitions. [2022-03-20 06:20:49,602 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2022-03-20 06:20:49,602 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 06:20:49,602 INFO L499 BasicCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:20:49,623 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-03-20 06:20:49,811 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-03-20 06:20:49,811 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 06:20:49,812 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 06:20:49,812 INFO L85 PathProgramCache]: Analyzing trace with hash -952273693, now seen corresponding path program 2 times [2022-03-20 06:20:49,812 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 06:20:49,812 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1778764166] [2022-03-20 06:20:49,812 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 06:20:49,812 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 06:20:49,820 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 06:20:49,820 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1720389529] [2022-03-20 06:20:49,820 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 06:20:49,820 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 06:20:49,821 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 06:20:49,825 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 06:20:49,826 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-03-20 06:20:49,894 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 06:20:49,894 INFO L229 tOrderPrioritization]: Conjunction of SSA is sat [2022-03-20 06:20:49,894 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-03-20 06:20:49,914 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-03-20 06:20:49,966 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-03-20 06:20:49,967 INFO L618 BasicCegarLoop]: Counterexample is feasible [2022-03-20 06:20:49,968 INFO L788 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-03-20 06:20:49,989 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-03-20 06:20:50,187 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-03-20 06:20:50,190 INFO L719 BasicCegarLoop]: Path program histogram: [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 06:20:50,192 INFO L180 ceAbstractionStarter]: Computing trace abstraction results [2022-03-20 06:20:50,223 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.03 06:20:50 BasicIcfg [2022-03-20 06:20:50,223 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-03-20 06:20:50,224 INFO L158 Benchmark]: Toolchain (without parser) took 63332.81ms. Allocated memory was 183.5MB in the beginning and 319.8MB in the end (delta: 136.3MB). Free memory was 126.4MB in the beginning and 279.5MB in the end (delta: -153.1MB). There was no memory consumed. Max. memory is 8.0GB. [2022-03-20 06:20:50,224 INFO L158 Benchmark]: CDTParser took 0.22ms. Allocated memory is still 183.5MB. Free memory is still 142.9MB. There was no memory consumed. Max. memory is 8.0GB. [2022-03-20 06:20:50,224 INFO L158 Benchmark]: CACSL2BoogieTranslator took 278.60ms. Allocated memory was 183.5MB in the beginning and 266.3MB in the end (delta: 82.8MB). Free memory was 125.9MB in the beginning and 240.0MB in the end (delta: -114.0MB). Peak memory consumption was 14.7MB. Max. memory is 8.0GB. [2022-03-20 06:20:50,224 INFO L158 Benchmark]: Boogie Preprocessor took 52.74ms. Allocated memory is still 266.3MB. Free memory was 240.0MB in the beginning and 238.4MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-03-20 06:20:50,224 INFO L158 Benchmark]: RCFGBuilder took 382.97ms. Allocated memory is still 266.3MB. Free memory was 238.4MB in the beginning and 226.9MB in the end (delta: 11.5MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-03-20 06:20:50,224 INFO L158 Benchmark]: IcfgTransformer took 68.68ms. Allocated memory is still 266.3MB. Free memory was 226.9MB in the beginning and 225.3MB in the end (delta: 1.6MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-03-20 06:20:50,224 INFO L158 Benchmark]: TraceAbstraction took 62538.49ms. Allocated memory was 266.3MB in the beginning and 319.8MB in the end (delta: 53.5MB). Free memory was 224.8MB in the beginning and 279.5MB in the end (delta: -54.7MB). There was no memory consumed. Max. memory is 8.0GB. [2022-03-20 06:20:50,225 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.22ms. Allocated memory is still 183.5MB. Free memory is still 142.9MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 278.60ms. Allocated memory was 183.5MB in the beginning and 266.3MB in the end (delta: 82.8MB). Free memory was 125.9MB in the beginning and 240.0MB in the end (delta: -114.0MB). Peak memory consumption was 14.7MB. Max. memory is 8.0GB. * Boogie Preprocessor took 52.74ms. Allocated memory is still 266.3MB. Free memory was 240.0MB in the beginning and 238.4MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 382.97ms. Allocated memory is still 266.3MB. Free memory was 238.4MB in the beginning and 226.9MB in the end (delta: 11.5MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * IcfgTransformer took 68.68ms. Allocated memory is still 266.3MB. Free memory was 226.9MB in the beginning and 225.3MB in the end (delta: 1.6MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * TraceAbstraction took 62538.49ms. Allocated memory was 266.3MB in the beginning and 319.8MB in the end (delta: 53.5MB). Free memory was 224.8MB in the beginning and 279.5MB in the end (delta: -54.7MB). There was no memory consumed. Max. memory is 8.0GB. * 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: 17]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L22] int counter = 0; VAL [\old(counter)=11, counter=0] [L24] int A, B; [L25] int r, d, p, q; [L26] A = __VERIFIER_nondet_int() [L27] B = 1 [L29] r = A [L30] d = B [L31] p = 1 [L32] q = 0 VAL [\old(counter)=0, A=7, B=1, counter=0, d=1, p=1, q=0, r=7] [L34] EXPR counter++ VAL [\old(counter)=0, A=7, B=1, counter=1, counter++=0, d=1, p=1, q=0, r=7] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, \old(counter)=0, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=1] [L35] RET __VERIFIER_assert(q == 0) VAL [\old(counter)=0, A=7, B=1, counter=1, d=1, p=1, q=0, r=7] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, \old(counter)=0, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=1] [L36] RET __VERIFIER_assert(r == A) VAL [\old(counter)=0, A=7, B=1, counter=1, d=1, p=1, q=0, r=7] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, \old(counter)=0, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=1] [L37] RET __VERIFIER_assert(d == B * p) VAL [\old(counter)=0, A=7, B=1, counter=1, d=1, p=1, q=0, r=7] [L38] COND FALSE !(!(r >= d)) [L40] d = 2 * d [L41] p = 2 * p VAL [\old(counter)=0, A=7, B=1, counter=1, d=2, p=2, q=0, r=7] [L34] EXPR counter++ VAL [\old(counter)=0, A=7, B=1, counter=2, counter++=1, d=2, p=2, q=0, r=7] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, \old(counter)=0, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=2] [L35] RET __VERIFIER_assert(q == 0) VAL [\old(counter)=0, A=7, B=1, counter=2, d=2, p=2, q=0, r=7] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, \old(counter)=0, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=2] [L36] RET __VERIFIER_assert(r == A) VAL [\old(counter)=0, A=7, B=1, counter=2, d=2, p=2, q=0, r=7] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, \old(counter)=0, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=2] [L37] RET __VERIFIER_assert(d == B * p) VAL [\old(counter)=0, A=7, B=1, counter=2, d=2, p=2, q=0, r=7] [L38] COND FALSE !(!(r >= d)) [L40] d = 2 * d [L41] p = 2 * p VAL [\old(counter)=0, A=7, B=1, counter=2, d=4, p=4, q=0, r=7] [L34] EXPR counter++ VAL [\old(counter)=0, A=7, B=1, counter=3, counter++=2, d=4, p=4, q=0, r=7] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, \old(counter)=0, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=3] [L35] RET __VERIFIER_assert(q == 0) VAL [\old(counter)=0, A=7, B=1, counter=3, d=4, p=4, q=0, r=7] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, \old(counter)=0, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=3] [L36] RET __VERIFIER_assert(r == A) VAL [\old(counter)=0, A=7, B=1, counter=3, d=4, p=4, q=0, r=7] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, \old(counter)=0, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=3] [L37] RET __VERIFIER_assert(d == B * p) VAL [\old(counter)=0, A=7, B=1, counter=3, d=4, p=4, q=0, r=7] [L38] COND FALSE !(!(r >= d)) [L40] d = 2 * d [L41] p = 2 * p VAL [\old(counter)=0, A=7, B=1, counter=3, d=8, p=8, q=0, r=7] [L34] EXPR counter++ VAL [\old(counter)=0, A=7, B=1, counter=4, counter++=3, d=8, p=8, q=0, r=7] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, \old(counter)=0, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=4] [L35] RET __VERIFIER_assert(q == 0) VAL [\old(counter)=0, A=7, B=1, counter=4, d=8, p=8, q=0, r=7] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, \old(counter)=0, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=4] [L36] RET __VERIFIER_assert(r == A) VAL [\old(counter)=0, A=7, B=1, counter=4, d=8, p=8, q=0, r=7] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, \old(counter)=0, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=4] [L37] RET __VERIFIER_assert(d == B * p) VAL [\old(counter)=0, A=7, B=1, counter=4, d=8, p=8, q=0, r=7] [L38] COND TRUE !(r >= d) VAL [\old(counter)=0, A=7, B=1, counter=4, d=8, p=8, q=0, r=7] [L44] EXPR counter++ VAL [\old(counter)=0, A=7, B=1, counter=5, counter++=4, d=8, p=8, q=0, r=7] [L44] COND TRUE counter++<5 [L45] CALL __VERIFIER_assert(A == q*B + r) VAL [\old(cond)=1, \old(counter)=0, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=5] [L45] RET __VERIFIER_assert(A == q*B + r) VAL [\old(counter)=0, A=7, B=1, counter=5, d=8, p=8, q=0, r=7] [L46] CALL __VERIFIER_assert(d == B*p) VAL [\old(cond)=1, \old(counter)=0, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=5] [L46] RET __VERIFIER_assert(d == B*p) VAL [\old(counter)=0, A=7, B=1, counter=5, d=8, p=8, q=0, r=7] [L48] COND FALSE !(!(p != 1)) [L50] d = d / 2 [L51] p = p / 2 VAL [\old(counter)=0, A=7, B=1, counter=5, d=4, p=4, q=0, r=7] [L52] COND TRUE r >= d [L53] r = r - d [L54] q = q + p VAL [\old(counter)=0, A=7, B=1, counter=5, d=4, p=4, q=4, r=3] [L44] EXPR counter++ VAL [\old(counter)=0, A=7, B=1, counter=6, counter++=5, d=4, p=4, q=4, r=3] [L44] COND FALSE !(counter++<5) [L58] CALL __VERIFIER_assert(A == d*q + r) VAL [\old(cond)=0, \old(counter)=0, counter=6] [L15] COND TRUE !(cond) VAL [\old(cond)=0, \old(counter)=0, cond=0, counter=6] [L17] reach_error() VAL [\old(cond)=0, \old(counter)=0, cond=0, counter=6] - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 31 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 62.4s, OverallIterations: 17, TraceHistogramMax: 15, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 27.3s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 2 mSolverCounterUnknown, 504 SdHoareTripleChecker+Valid, 14.3s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 444 mSDsluCounter, 2966 SdHoareTripleChecker+Invalid, 14.0s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2222 mSDsCounter, 372 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1697 IncrementalHoareTripleChecker+Invalid, 2071 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 372 mSolverCounterUnsat, 744 mSDtfsCounter, 1697 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1301 GetRequests, 1163 SyntacticMatches, 13 SemanticMatches, 125 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 123 ImplicationChecksByTransitivity, 18.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=212occurred in iteration=11, InterpolantAutomatonStates: 126, 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, 16 MinimizatonAttempts, 111 StatesRemovedByMinimization, 13 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.4s SatisfiabilityAnalysisTime, 30.7s InterpolantComputationTime, 861 NumberOfCodeBlocks, 861 NumberOfCodeBlocksAsserted, 20 NumberOfCheckSat, 1283 ConstructedInterpolants, 0 QuantifiedInterpolants, 17980 SizeOfPredicates, 33 NumberOfNonLiveVariables, 2039 ConjunctsInSsa, 183 ConjunctsInUnsatCore, 24 InterpolantComputations, 9 PerfectInterpolantSequences, 3212/3666 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-03-20 06:20:50,261 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...