Multiway Decision Graphs (MDGs) are special decision diagrams that subsume Binary Decision Diagrams (BDDs) and extend them by a first-order formulae suitable for model checking of data path circuits. Satisfiability Checking (SAT) has emerged recently as an alternative for decision graphs. Their performance is less sensitive to the problem sizes and they do not suffer from state space explosion. In this paper, we propose a model checking methodology that allows to combine tightly MDGs and SAT. We use a rewriting based SAT solver to prune the transition relation of the circuits to produce a smaller one that is fed to the MDG model checker. We support our reduction methodology by experimental results executed on benchmark properties.

Binary decision diagram

Benchmark (surveying)

Boolean satisfiability problem

Satisfiability

Solver

10.1109/icm.2007.4497677

Cite

Citations (12)

PARTCAT: A Subspace Clustering Algorithm for High Dimensional Categorical Data

The 2006 IEEE International Joint Conference on Neural Network Proceedings (2006)

Guojun Gan Jian Wu Zijiang Yang

A new subspace clustering algorithm, PARTCAT, is proposed to cluster high dimensional categorical data. The architecture of PARTCAT is based on the recently developed neural network architecture PART, and a major modification is provided in order to deal with categorical attributes. PARTCAT requires less number of parameters than PART, and in particular, PARTCAT does not need the distance parameter that is needed in PART and is intimately related to the similarity in each fixed dimension. Some simulations using real data sets to show the performance of PARTCAT are provided.

Categorical variable

Similarity (geometry)

Clustering high-dimensional data

10.1109/ijcnn.2006.247041

Cite

Citations (14)

SIGRNN: Synthetic Minority Instances Generation in Imbalanced Datasets using a Recurrent Neural Network

Reda Al-Bahrani Dipendra Jha Qiao Kang Sunwoo Lee Zijiang Yang

10.5220/0010348103490356

Cite

Citations (1)

Solving partially observable problems with inaccurate PSR models

Information Sciences (2014)

Yunlong Liu Zijiang Yang Guoli Ji

10.1016/j.ins.2014.06.034

Cite

Citations (6)

Tell You a Definite Answer: Whether Your Data is Tainted During Thread Scheduling

IEEE Transactions on Software Engineering (2018)

Xiaodong Zhang Zijiang Yang Qinghua Zheng Hao Yu Pei Liu

With the advent of multicore processors, there is a great need to write parallel programs to take advantage of parallel computing resources. However, due to the nondeterminism of parallel execution, the malware behaviors sensitive to thread scheduling are extremely difficult to detect. Dynamic taint analysis is widely used in security problems. By serializing a multithreaded execution and then propagating taint tags along the serialized schedule, existing dynamic taint analysis techniques lead to under-tainting with respect to other possible interleavings under the same input. In this paper, we propose an approach called DSTAM that integrates symbolic analysis and guided execution to systematically detect tainted instances on all possible executions under a given input. Symbolic analysis infers alternative interleavings of an executed trace that cover new tainted instances, and computes thread schedules that guide future executions. Guided execution explores new execution traces that drive future symbolic analysis. We have implemented a prototype as part of an educational tool that teaches secure C programming, where accuracy is more critical than efficiency. To the best of our knowledge, DSTAM is the first algorithm that addresses the challenge of taint analysis for multithreaded program under fixed inputs.

Taint checking

Serialization

Symbolic data analysis

10.1109/tse.2018.2871666

Cite

Citations (3)