  Program invariants are important for defect detection, program verification,
and program repair. However, existing techniques have limited support for
important classes of invariants such as disjunctions, which express the
semantics of conditional statements. We propose a method for generating
disjunctive invariants over numerical domains, which are inexpressible using
classical convex polyhedra. Using dynamic analysis and reformulating the
problem in non-standard "max-plus" and "min-plus" algebras, our method
constructs hulls over program trace points. Critically, we introduce and infer
a weak class of such invariants that balances expressive power against the
computational cost of generating nonconvex shapes in high dimensions.
  Existing dynamic inference techniques often generate spurious invariants that
fit some program traces but do not generalize. With the insight that generating
dynamic invariants is easy, we propose to verify these invariants statically
using k-inductive SMT theorem proving which allows us to validate invariants
that are not classically inductive.
  Results on difficult kernels involving nonlinear arithmetic and abstract
arrays suggest that this hybrid approach efficiently generates and proves
correct program invariants.
