Experimental analyses of the K-hidden algorithm. (June 2017)

• Record Type: Journal Article
• Authors: Zhao, Dongdong; Luo, Wenjian; Liu, Ran; Yue, Lihua
• Is Part Of: Engineering applications of artificial intelligence. Volume 62(2017:Feb.)
• Page Start: 331
• Page End: 340
• Publication Date: 2017-06
• Subjects: Data security -- Privacy protection -- Negative database -- SAT solver; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2016.05.010
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: The K -hidden algorithm is proposed in our previous work, and it is a more fine-grained algorithm for generating negative databases ( NDB s). The hardness of reversing the K -hidden- NDB (i.e., the NDB that is generated by the K -hidden algorithm) by the local search strategy and the Unit Clause heuristics has been analyzed in theory in the previous work. It was demonstrated that the K -hidden- NDB could be more hard-to-reverse (with regard to the local search strategy) and diverse than the p -hidden- NDB and q -hidden- NDB ( NDB s that are generated by the typical p -hidden algorithm and q -hidden algorithm, respectively). However, no experiments was carried out in the previous work to verify the hardness of reversing the K -hidden- NDB and its diversity. In this paper, several experiments, which employ three SAT solvers, are carried out to verify the hardness of reversing the K -hidden- NDB and its diversity. Two solvers are traditional SAT solvers (i.e., WalkSAT and zChaff) based on the local search strategy and the Unit Clause heuristics, respectively, and they are widely used in verifying the hardness of SAT instances and reversing NDB s. Another one is a state-of-the-art SAT solver, which won the gold prize of the Sequential Random SAT Track in SAT Competition 2014.