Author name cluster

Depeng Liu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

TCS Journal 2023 Journal Article

Model checking differentially private properties

Depeng Liu
Bow-Yaw Wang
Chen Fu
Lijun Zhang

With the explosion of digital data collected from social apps, privacy protection regulations have been issued by almost all countries. Differential privacy is proposed as a successful technique to make use of these data, without leaking personal private data at the same time. In this paper, we investigate logical reasoning for differential privacy properties and propose model checking algorithms. We introduce the branching time temporal logic dpCTL* to specify differentially private properties. Several mechanisms in differential privacy are formalized as Markov chains or Markov decision processes. In our framework, we show that subtle privacy conditions are specified by dpCTL*. In order to verify privacy properties automatically, model checking problems are investigated. We develop a model checking algorithm for Markov chains. Model checking dpCTL* properties on Markov decision processes however is shown to be undecidable. Therefore, we propose a sound algorithm to verify these properties in Markov decision processes. We implement our model checking algorithm into a tool, based on the PRISM language, as well as show the experimental results and a case study of stream processing in differential privacy under the essential fairness assumptions.

Details DOI

I&C Journal 2021 Journal Article

A novel learning algorithm for Büchi automata based on family of DFAs and classification trees

Yong Li
Yu-Fang Chen
Lijun Zhang
Depeng Liu

In this paper, we propose a novel algorithm to learn a Büchi automaton from a teacher who knows an ω-regular language. The learned Büchi automaton can be a nondeterministic Büchi automaton or a limit deterministic Büchi automaton. The learning algorithm is based on learning a formalism called family of DFAs (FDFAs) recently proposed by Angluin and Fisman. The main catch is that we use a classification tree structure instead of the standard observation table structure. The worst case storage space required by our algorithm is quadratically better than that required by the table-based algorithm proposed by Angluin and Fisman. We implement the proposed learning algorithms in the learning library ROLL (Regular Omega Language Learning), which also consists of other complete ω-regular learning algorithms available in the literature. Experimental results show that our tree-based learning algorithms have the best performance among others regarding the number of solved learning tasks.

Details DOI