IvcMcsComputation of Inductive Validity Cores and Maximal Unsafe Abstractions / Minimal Cut Sets
This implementation is inspired from the following paper:
Berryhill, Ryan & Veneris, Andreas. (2019). Chasing Minimal Inductive Validity Cores in Hardware Model Checking. 19-27. 10.23919/FMCAD.2019.8894268.
type 'a analyze_func =
bool ->
bool ->
bool ->
Lib.kind_module list ->
'a InputSystem.t ->
Analysis.param ->
TransSys.t ->
unitval complement_of_ivc : 'a InputSystem.t -> TransSys.t -> ivc -> ivccomplement_of_ivc in_sys sys ivc returns the complement of ivc. The parameters in_sys and sys must be the same as the ones used to generate ivc.
separate_ivc_by_category scope ivc separates ivc into two IVCs: the first one only contains elements from the categories selected by the user, and the second one contains the remaining elements of ivc. The parameter scope should refer to the top-level system the ivc was generated from.
val minimize_lustre_ast :
?valid_lustre:bool ->
'a InputSystem.t ->
ivc ->
LustreAst.t ->
LustreAst.tminimize_lustre_ast in_sys ivc ast minimizes the lustre AST ast according to the inductive validity core ivc. The parameters in_sys should be the same as the one used to generate ivc. The optional parameter valid_lustre (default: false) determine whether the generated AST must be a valid lustre program or a more concise and easily readable program.
val is_ivc_approx : ivc -> boolval ivc_uc :
'a InputSystem.t ->
?approximate:bool ->
TransSys.t ->
Property.t list ->
ivc resultivc_uc in_sys sys props computes an approximation of a minimal inductive validity core for the input system in_sys and the transition system sys. Only properties props are considered. The optional parameter approximate determines whether the unsat core computed internally must be minimal or not (in any case, the resulting IVC is NOT guaranteed to be minimal).
val must_set :
'a InputSystem.t ->
Analysis.param ->
'a analyze_func ->
TransSys.t ->
Property.t list ->
ivc resultmust_set in_sys param analyze_func sys props computes the MUST set for the input system in_sys, the analysis parameter param and the transition system sys. Only properties props are considered.
val ivc_ucbf :
'a InputSystem.t ->
?use_must_set:(ivc -> unit) option ->
Analysis.param ->
'a analyze_func ->
TransSys.t ->
Property.t list ->
ivc resultivc_ucbf in_sys param analyze_func sys props computes a minimal inductive validity core for the input system in_sys, the analysis parameter param and the transition system sys. Only properties props are considered. This function first computes an approximation of a minimal IVC, and then tries to reduce it further. Most of time, it is faster than using ivc_bf. If the optional parameter use_must_set is not None, a MUST set will be computed first and passed to the given continuation.
val umivc :
'a InputSystem.t ->
?use_must_set:(ivc -> unit) option ->
?stop_after:int ->
Analysis.param ->
'a analyze_func ->
TransSys.t ->
Property.t list ->
int ->
(ivc -> unit) ->
bool * ivc listumivc in_sys param analyze_func sys props k cont computes all minimal inductive validity cores for the input system in_sys, the analysis parameter param and the transition system sys. Only properties props are considered. Each IVC is passed to the continuation cont as soon as it is found. The parameter k determines up to which cardinality MCSes must be computed before starting searching for IVC. A value of -1 will compute all the MCSes, and in this case the first IVC found is guaranteed to have a minimal cardinality. If the optional parameter use_must_set is not None, a MUST set will be computed first and passed to the given continuation. If stop_after is n > 0, the search will stop after n minimal IVCs being found. This function returns a couple (isComplete, ivcs) with isComplete being a boolean that indicates whether the solutions found cover all the real solutions or not (it might not be the case in case of a timeout).
val complement_of_mcs : 'a InputSystem.t -> TransSys.t -> mcs -> mcscomplement_of_mcs in_sys sys mcs returns the complement of mcs (the complement of a MCS is a MUA). The parameters in_sys and sys must be the same as the ones used to generate mcs.
separate_mcs_by_category scope mcs separates mcs into two MCSes: the first one only contains elements from the categories selected by the user, and the second one contains the remaining elements of mcs. The parameter scope should refer to the top-level system the mcs was generated from.
val is_mcs_approx : mcs -> boolval mcs :
'a InputSystem.t ->
Analysis.param ->
'a analyze_func ->
TransSys.t ->
Property.t list ->
?initial_solution:mcs option ->
?max_mcs_cardinality:int ->
bool ->
bool ->
(mcs -> unit) ->
bool * mcs listmcs in_sys param analyze_func sys props all cont computes a maximal unsafe abstraction for the input system in_sys, the analysis parameter param and the transition system sys. Only properties props are considered. If all is true, all the MCSes will be computed. Each MCS is passed to the continuation cont as soon as it is found. If the optional parameter max_mcs_cardinality is n >= 0, only MCSes of cardinality greater or equal to (total_number_of_model_elements - n) will be computed. If a global initial MCS analysis has been performed, its result should be passed in initial_solution, otherwise you can omit this parameter. This function returns a couple (isComplete, mcs) with isComplete being a boolean that indicates whether the solutions found cover all the real solutions or not (it might not be the case in case of a timeout).
val mcs_initial_analysis :
'a InputSystem.t ->
Analysis.param ->
'a analyze_func ->
?max_mcs_cardinality:int ->
TransSys.t ->
(Property.t * mcs) listval ivc_to_print_data :
'a InputSystem.t ->
TransSys.t ->
string ->
float option ->
ivc ->
ModelElement.core_print_dataval mcs_to_print_data :
'a InputSystem.t ->
TransSys.t ->
string ->
float option ->
mcs ->
ModelElement.core_print_dataval pp_print_mcs_legacy :
'a InputSystem.t ->
Analysis.param ->
TransSys.t ->
mcs ->
mcs ->
unitval pp_print_no_mcs_legacy : Property.t -> TransSys.t -> unit