Information-Theoretic Opacity-Enforcement in Markov Decision Processes

1 Introduction

Opacity, as a plural concept, has been proposed to generalize secrecy, anonymity, privacy, and other confidentiality properties against attacks [Zeng and Koutny, 2021; Watson, 2011; Guo et al., 2020]. Opacity enforcement is to hide sensitive information from an external observer.

Depending on the various measures of opacity, two classes of opacity enforcement problems have been investigated: Qualitative opacity enforcement requires that an adversary/observer, with complete knowledge of the system yet noisy observations, can ascertain some "secret" information of the system with probability one. Quantitative opacity enforcement, on the other hand, requires that the observer's uncertainty in guessing the secret after receiving the observations is close to the uncertainty the observer initially had. Connecting with the classical work of Shannon on secrecy [Shannon, 1949] and guesswork [Khouzani and Malacaria, 2017], we propose to measure quantitative opacity using the conditional entropy of the random variable (e.g. the observer's estimate of a secret variable Z) given the observed information (e.g. the observation sequence Y ). This is because the leaked information =

initial uncertainty

︸ ︷︷ ︸ H(Z)-"entropy before observation"

- remaining uncertainty

︸ ︷︷ ︸ H(Z|Y )-" entropy after observation"

The more opaque the system is, the larger the entropy after the observation. With this notion of quantitative opacity, we study optimal opacity-enforcement planning in a stochastic system modeled as a Markov decision process (MDP) subject to task performance constraints. We consider the interaction between a planning agent (referred to as player 1/P1) and an observer (referred to as player 2/P2). The goal of P1 is to maximize the opacity while ensuring that the total return meets a satisfying threshold, against P2 who has partial observations about the system trajectories but complete knowledge about the system model and P1's control policy. Two problems of state-based opacity are studied. One is the last-state opacity, where P1 aims to obfuscate if the last state is in a set of secret states, to P2. The other one is initial-state opacity, where P1 aims to obfuscate the exact initial state to P2.

Related Work Opacity was originally introduced by Mazar´e [2004], referring to concealing secrets from an observer. This work has led to qualitative opacity analyses within discrete event systems (DESs), where the system dynamics are governed by both controllable and uncontrollable events, and its information leakage is also defined by observable and nonobservable events. In qualitative analysis, a trajectory is opaque if it satisfies some secret property and is indistinguishable from at least one trajectory that does not satisfy the secret. Furthermore, a system is opaque if it generates only an opaque trajectory. Different types of qualitative opacity have been studied, including state-based, which requires the secret behavior of the system (i.e., the membership of its initial/current/past state to the set) to remain opaque [Saboori and Hadjicostis, 2007; Saboori and Hadjicostis, 2013a; Han et al., 2023; Saboori and Hadjicostis, 2013b; Saboori and Hadjicostis, 2009; Yin et al., 2019]; language-based [Dubreil

.

et al., 2008; Lin, 2011; Shi et al., 2023], which aims to hide a set of secret executions; and "model-based" [Keroglou and Hadjicostis, 2016], aiming to prevent the observer from finding out the true model of the system among several candidates. In multi-agent deterministic systems, cooperative privacy-preserving planning has been investigated [Maliah et al., 2017; Shani, 2018] to achieve a global coordinated plan without revealing local private information.

A quantitative analysis of opacity is essential for measuring the degree of opacity in a system. [B´erard et al., 2015a] defines quantitative opacity as the probability of generating an opaque run in a stochastic system. A related notion to quantitative opacity is covertness [Marzouqi and Jarvis, 2004; Marzouqi and Jarvis, 2005], which can be viewed as a modelbased opacity, as it makes the observer uncertain if a covert agent is present or not. Recent work [Ma et al., 2023] developed covert planner that leverages the coupling of stochastic dynamics and observational noises to make the covert agent's policy indistinguishable from a nominal policy. Informationtheoretic opacity has been studied in channel design problems, which can be viewed as a one-step decision-making problem[Khouzani and Malacaria, 2017]. Another recent work [Molloy and Nair, 2023] developed a method for obfuscating state trajectories in partially observable Markov decision processes (POMDPs) and shows that the causal conditional entropy of the state trajectory can be expressed into a cumulative sum, permitting the use of POMDP solvers. Our work is also related to observer-aware MDP [Miura and Zilberstein, 2021] in the sense that one of the reward functions depends on the observer's belief (of the secret). However, our solution does not employ POMDP solvers.

Our Contribution Our work can be seen as a generalization of minimal information leakage channel design from one-stage decision-making to sequential decision-making in Markov decision processes, concerning state-based opacity. We establish the last-state opacity and initial-state opacity by leveraging Shannon entropy [Shannon, 1949] as a symmetric measure of opacity. Different from Molloy and Nair [2023], we do not assume that the observer has access to control inputs. Thus, the conditional entropy of state-based opacity properties cannot be constructed as a cumulative sum of entropy terms. We propose a novel approach to compute/estimate the gradient of the conditional entropy with respect to (w.r.t.) the parameters of the control policy, leveraging the forward-backward algorithm in HMMs. Building on the gradient estimation/computation, we can then formulate the optimal opacity enforcement planning problem, subject to task constraints, into a constrained optimization and employ primal-dual gradient-based optimization to compute a (locally)-optimal policy that maximizes the opacity while satisfying a constraint on the total return. The correctness of the proposed methods is experimentally validated.

2 Preliminary and ProblemFormulation

2.1 Preliminaries

Notation The set of real numbers is denoted by R. Random variables will be denoted by capital letters, and their realizations by lowercase letters (e.g., X and x). The probability mass function (pmf) of a discrete random variable X will be written as p(x), the joint pmf of X and Y as p(x, y), and the conditional pmf of X given Y = y as p(x|y) or p(x|Y = y). The sequence of random variables and their realizations with length T are denoted as X[0:T ] and x[0:T ], respectively. Given a finite and discrete set S, let D(S) be the set of all probability distributions over S. The set S T denotes the set of sequences with length T composed of elements from S, and S ∗ denotes the set of all finite sequences generated from S.

The Planning Problem The problem is modeled as an MDP M = ⟨S,A, P, µ0,R, γ⟩ where S is a finite set of states, A is a finite set of actions, P : S × A → D(S) is a probabilistic transition function and P(s′ |s, a) is the probability of reaching state s′ given that action a is taken at the state s, and µ0 is the initial state distribution. The planning objective is described by a reward function R : S × A → R. γ ∈ [0, 1] is the discount factor.

We refer to the planning agent as player 1, or P1, and the observer as player 2, or P2. For a Markov policy π : S → D(A), P1's value function V π : S → R is defined as

where Eπ is the expectation w.r.t. the probability distribution induced by the policy π from M. We denote the Markov chain induced by the policy π as Mπ. And Sk is the k-th state in the Markov chain Mπ. P2's observation function is a common knowledge, defined as follows:

Definition 1 (Observation function of P2). Let O be a finite set of observations. The state-observation function of P2 is Obs : S → D(O) that maps a state s to a distribution Obs(s) in the observation space. The action is non-observable.

Note that the assumption on non-observable actions can be easily relaxed, by augmenting the state space with S∪(S×A) and defining the state-observation function over the augmented state space. This assumption is made for clarity.

For an MDP M and P2's observation function Obs, a policy π induces a discrete stochastic process {St,Ot, t ∈ N} where each St ∈ S and Ot ∈ O. For a Markov policy,

Next, we will introduce some basic definitions in information theory that are used to quantify the opacity of a policy.

The entropy of a random variable X with a countable support X and a probability mass function p is

The joint entropy of two random variables X1,X2 with the same support X is

The conditional entropy of X2 given X1 is

The conditional entropy measures the uncertainty about X2 given knowledge of X1. It is defined as

A higher conditional entropy makes it more challenging to infer X2 fromX1.

2.2 Problem Statement

Definition 2. Given the MDP M and a policy π induce a discrete stochastic process Mπ = {St, Ot, t ∈ N} with T > 0 a finite number. Let E be a set of secret states. For any 0 ≤ t ≤ T , let the random variable Zt be defined by

That is, Zt is the random variable representing if the t-th state is in the set of secret states. The random variables Zt are binary Z = {0, 1}, for each 0 ≤ t ≤ T .

The conditional entropy of Zt given an observation Y = O[0:T] is defined as

where P Mπ (Zt = z, y) is the joint probability of Zt = z (for z = 0, 1) and observation y given the stochastic process Mπ and P Mπ (z|Y = y) is the conditional probability of z given the observation y and OT is the sample space for the observation sequence of length T. This conditional entropy [Shannon, 1949] can be interpreted as the fewest number of subset-membership queries an adversary must make before discovering the secret.

Based on the notion of information leakage [Yasuoka and Terauchi, 2010], the quantitative analysis of confidential information of a dynamical system is defined as the difference between an attacker's capability in guessing the secret before and after available observations about the system. Thus, the maximal opacity-enforcement planning with task constraints can be formulated as the following problem:

Problem 1 (Maximal last-state opacity). Given the MDPM, a set E of secret states, a finite horizon T, compute a policy that maximizes the conditional entropy H(ZT |Y ; Mπ) between the random variable ZT and the observation sequence Y = O[0:T] while ensuring the total discounted reward exceeds a given threshold δ.

In other words, the objective is to ensure the adversary, with the knowledge of the agent's policy and the observations, is maximally uncertain regarding whether the last state of a finite path is in the secret set. This symmetric notion of opacity implies that opacity will be minimal when the observer is consistently confident that the agent either visited or avoided the secret states given an observation. This stands in contrast to asymmetric opacity [B´erard et al., 2015b], which only assesses the uncertainty regarding the visits of secrets. Meanwhile, the agent is required to get an adequate total reward (no less than δ) to achieve a satisfactory task performance.

We also consider the problem of hiding the initial state. We assume that the observer has the complete knowledge of MDP, and thereby knows the initial state distribution µ0. Then, the nature selects one of the initial states probabilistically according to µ0, says s0. The agent aims to hide the actual realization of the initial state s0 from the observer.

Problem 2 (Maximal initial-state opacity). Given the MDP M, a finite horizon T, and the initial state distribution µ0. Compute a policy that maximizes the conditional entropy H(S0|Y ;Mπ) between the initial state S0 and the observation sequence Y = O[0:T ] while ensuring the total discounted reward exceeds a given threshold δ.

3 SynthesizingMaximally Opacity-Enforcement Controllers For Last-state Opacity

3.1 Primal-Dual Policy Gradient for Constrained Minimal Information Leakage

For clarity in notation, we consider a finite state set S = {1, . . . ,N}. We introduce a set of parameterized Markov policies {πθ | θ ∈ Θ} where Θ is a finite-dimensional parameter space. For any Markov policy πθ parameterized by θ, the Markov chain induced by πθ from M is denoted Mθ : {St,At, t ≥ 0} where St is the random variable for the t-th state and At is the random variable for the t-th action. The transition kernel of the Markov chain is Pθ such that Pθ(i, j) = ∑a∈A P(j|i, a)πθ(a|i) is the probability of moving from state i to j in one step.

The maximal last-state opacity-enforcement planning problem can be formulated as a constrained optimization problem as follows:

where δ is a lower bound on the value function. The value V (µ0, θ) is obtained by evaluating the policy πθ given the initial state distribution µ0, i.e., V (µ0, θ) := V πθ (µ0), and H(ZT |Y ; θ) := H(ZT |Y ;Mθ).

For this constrained optimization problem with an inequality constraint, we formulate the problem (2) into the following max-min problem for the associated Lagrangian L(θ, λ):

where λ is the multiplier.

In each iteration k, the primal-dual gradient descent-ascent algorithm is given as

where η > 0, κ > 0 are step sizes. And the gradient of Lagrangian function w.r.t. θ can be computed as

The term ∇θV (µ0, θ) can be easily computed by the standard policy gradient algorithm [Sutton et al., 1999].

Following the primal-dual gradient descent-ascent method, we need to compute the gradient of the conditional entropy w.r.t. the policy parameter θ. This is nontrivial because this conditional entropy is non-cumulative. Next, we show how to employ the forward algorithm in Hidden Markov Model (HMM) to compute such a gradient ∇θH(ZT |Y ; θ).

3.2 Computing the Gradient of Conditional Entropy

From the observer's perspective, the stochastic process under policy πθ is a HMMHMθ = (S,O, Pθ,B), where S is the state space, O is the observation state space, Pθ is the transition kernel and B = {bi, i ∈ S} is the emission probability distributions where bi(o) = Obs(o|i). It is noted that the emission distributions do not depend on the policy.

The conditional entropy of ZT given an observation sequence Y can be written as

where the probability measure Pθ := P Mπθ . The discrete conditional entropy of a binary random variable has a property that 0 ≤ H(ZT |Y ; θ) ≤ 1. We take the gradient of H(ZT |Y ; θ) w.r.t. the policy parameter θ. By using a trick that ∇θP(y) = Pθ(y)∇θ logPθ(y) and the property of conditional probability, we have

We propose a novel approach to compute the gradients ∇θPθ(zT |y) and ∇θ logPθ(y) for zt ∈ {0, 1}. First, we introduce the concept of forward α messages from HMM [Baum et al., 1970]. Given a fixed observation sequence y = o[0:T], for each 0 ≤ t ≤ T, the forward α message at the time step t for a given state j is,

which is the joint probability of receiving observation o[0:t] and arriving at state j at the t-th time step. By definition of α messages and the law of total probability, the probability of receiving observation y is Pθ(y) = ∑i∈S αT (i, θ).

The forward α messages can be calculated recursively by the following equations,

for t = 0, . . . T. The initial forward α message is defined jointly by the initial observation and the initial state distribution, α0(j, θ) = µ0(j)bj(o0), 0 ≤ j ≤ N. Since ZT is the random variable to represent if the last state ST is in a set E of secret states, then

and the conditional probability Pθ(ZT = 1|y) is given by

The derivative of Pθ(zT |y) w.r.t. policy parameter θ can be computed as

where ∇θPθ(y) = ∑k∈S ∇θαT (k, θ). To obtain ∇θPθ(ZT = 0|y), we have Pθ(ZT = 0|y) = 1 - Pθ(ZT = 1|y). Thus, ∇θPθ(ZT = 0|y) = -∇θPθ(ZT = 1|y).

Thus, computing the gradient of Pθ(ZT = 1|y) and Pθ(ZT = 0|y) requires the gradients of all forward α messages w.r.t. the policy parameter θ. We can compute these gradients using the following recursive computation based on (9): For 1 ≤ t ≤ T ,

and ∇θα0(j, θ) = 0. It is observed that the set of forward α messages given the current policy πθ and a fixed observation y can be computed using (9). In addition, the gradient

can be computed using the current policy πθ and the gradient of the policy w.r.t. θ. Lastly, the transition kernel Pθ(i, j) and the emission probabilities are known or can be computed.

After computing ∇θPθ(ZT = 1|y), ∇θPθ(ZT = 0|y), and ∇θP (y), we can obtain the value of ∇θH(ZT |Y ; θ) by equation (7). It is noted that, though OT is a finite set of observations, it is combinatorial and may be too large to enumerate.

To mitigate this issue, we can employ sample approximations to estimate ∇θHθ(ZT |Y ): Given M sequences of observations {y1, . . . , yM}, we can approximate H(ZT |Y ; θ) by

∇θH(ZT |Y ; θ)

4 SynthesizingMaximally Opacity-Enforcement Controllers For Initial-state Opacity

In this subsection, we look into the initial-state opacity, measured by the conditional entropy H(S0|Y ; θ) of the initial state S0 given by the observation sequence Y , which is defined by:

The maximal opacity-enforcement planning for initialstate opacity can be formulated similarly as a constrained optimization problem:

where s0 ∈ S is the initial state sampled from µ0. In this optimization problem, we assume that s0 is known to the planning agent but not the observer.

For this constrained optimization problem with an inequality constraint, we formulate the problem (18) into the following max-min problem for the associated Lagrangian L(θ, λ):

where λ is the multiplier.

Following the similar primal-dual optimization approach (see (4)), we need to calculate the gradient of H(S0|Y ; θ) w.r.t. the policy parameter. Also, using a trick that ∇θP(y) = Pθ(y)∇θ logP(y), we have

The computations of Pθ(θ) and ∇θ log Pθ(y) are the same as those for the last-state opacity (see Section 3.2). In addition, for the initial-state opacity, we need to obtain the Pθ(s0|y) and its derivative w.r.t. θ.

FromBayes' theorem,

Note that µ0 is the prior distribution of the initial state, which is known and does not depend on θ. Thus, the gradient of Pθ(s0|y) w.r.t. θ is given by

To compute the Pθ(y|s0) and ∇θPθ(y|s0) for s0 ∈ S, we employ the backward β messages from HMM [Baum et al., 1970], defined as follows: Given a observation sequence o[t:T], for each 0 ≤ t ≤ T, the backward β message at the time step t for a given state i is,

which represents the probability of having the observation sequence o[t:T] given the state is i at time step t. It can be computed by the backward algorithm:

for t = 0, . . . T - 1, and βT (i, θ) = 1 for 1 ≤ i ≤ N. Also note that Pθ(y|i) = β0(i, θ) for each state in the support of the initial state distribution. By recursion, we can obtain Pθ(y|i) using the backward β messages. For each i ∈ Supp(µ0), we can also obtain the gradient of Pθ(y|i)

The computation of ∇θPθ(i, j) is in equation (14). In this way, H(S0|Y ; θ) and ∇θH(S0|Y ; θ) can be computed exactly. Again, since y ∈ OT is combinatorially many, we employ sample approximation to estimate the value. Given M trajectories {y1, . . . , yM}, the entropy term H(S0|Y ; θ) and the gradient term ∇θH(S0|Y ; θ) can be approximated by

and

With the above step of calculating the gradient of conditional entropy H(S0|Y ; θ) w.r.t. θ, we can then employ the primal-dual approach to solve a (local) optimal solution to Problem 2.

5 Experiment Evaluation

Example 1 (Grid World Example). The effectiveness of the proposed optimal opacity-enforcement planning algorithms 1 is illustrated through a stochastic grid world example shown in Figure 1. In this example, we focus on optimizing the laststate opacity and initial-state opacity. The details of the environment setting are outlined in Figure 1. For perception, four sensors are placed on the grid with distinct ranges indicated by the blue, red, yellow, and green areas in the picture. As P1 enters these sensor ranges, the observer receives corresponding observations ("b", "r", "y", "g", respectively) with probability p = 0.9 and a null observation ("0") with probability 1 - p = 0.1, attributed to the false negative rate of the sensors.

The question marks on the grid represent the secret states for P1, while the flags denote the goal states for P1. We set the reward of reaching a goal to be 0.1 and the constraint that the total return is greater than or equals δ = 0.3, and the horizon T = 10. Note that, in this finite horizon, the robot can repeatedly visit the goal state.

We will employ the soft-max policy parameterization, i.e.,

where θ ∈ R|S×A| is the policy parameter vector. The softmax policy has good analytical properties including completeness and differentiability.

1 The code of the experiment is available on https://github.com/ AronYoung414/leakage minial design MDP

During the optimization of last-state opacity, we maintain a fixed initial state for P1, given by the position of the robot illustrated in Figure 1. Figure 2a illustrates the estimated value of the last-state opacity and the total return within the primaldual policy gradient method. We use the estimated total return instead of the analytical total return from value iterations because we employ the gradient estimate of the total return in the proposed opacity-enforcement policy gradient method.

Figure 2a illustrates when the algorithm converges, the conditional entropy H(ZT |Y ) eventually approaches 0.930. The value of policy reaches 0.328, satisfying the predefined threshold of δ = 0.3. Given the conditional entropy is close to 1, which is the maximal value of the entropy, the observation reveals little information regarding whether a secret location is visited, even when the observer knows the exact policy used by the robot. The conditional entropy is inversely proportional to the value/total return. This behavior is a consequence of the environmental configuration. From observing the sampled trajectories, we noticed that the agent navigates among various sensor ranges to confuse the observer, thereby diminishing the total return that P1 can achieve, as P1 is constrained from remaining stationary at the goal.

During the optimization of initial-state opacity, the set of possible initial states is four corners (cells (0, 0), (0, 5), (5, 0), (5, 5)). The initial-state distribution follows a discrete uniform distribution across this set of initial states. Figure 2b illustrates the initial-state opacity, measured by the conditional entropy H(S0|Y ), and the value of the policy within the primal-dual policy gradient method. The same threshold δ = 0.3 is employed here. When the algorithm converges, the initial conditional entropy eventually reaches 0.329. The policy value reaches 0.301, satisfying the predefined threshold of δ = 0.3. In this environment, elevated initial-state opacity indicates the observer is less uncertain about P1's specific initial state. This result is understandable because the four sensors are highly sensitive to detect the presence of P1 in its range and different initial states give different sensor readings to the observer with high probabilities.

Since there are no other algorithms for solving the proposed opacity-enforcement planning problems, we consider a comparison with a baseline algorithm for entropy-regularized MDPs, where the objective value is a weighted sum of the total return and the discounted entropy of the policy [Nachum et al., 2017]. As the weight on the entropy terms increases, the policy is more stochastic and noisy.

The objective function for entropy-regularized MDPs is given by [Nachum et al., 2017; Cen et al., 2022]:

The discounted entropy term, H(s; θ), is defined as:

where dπθ is the occupancy measure induced by policy πθ. The objective is to maximize the regularized total return Vτ (s; θ).

We compare our method with entropy-regularized MDPs solved with different τ values, selecting 10 values from τ =

0.01 to τ = 0.1. The following graphs (Figure 3) illustrate the results. Note that, when τ = 0.1, the policy approaches a random policy, making it impractical to further increase opacity by raising τ .

The results in Figure 3 indicate that maximizing last-state opacity and initial-state opacity cannot be achieved using standard entropy-regularized MDP. In Figure 3a, we observed that, despite the increasing value for τ, the conditional entropy H(ZT |Y ) under the baseline algorithm remains below 0.4 and below the value obtained with the proposed method, indicating that the observer has more certainty in predicting if a secret state is visited. The value of the policy decreases as τ increases, and when τ ≥ 0.03, the entropy-regulated policy fails to satisfy the constraint on the total return. Our method outperforms this baseline by attaining the value of 0.3 with a last-state opacity of 0.930. Figure 3b shows that the initial-state opacity fluctuates with increasing τ but does not reach the optimal initial-state opacity (0.329) achieved by our method.

These comparison experiments indicate that our proposed methods could exploit the noise in the observation to optimize opacity. This feature is not achievable using a policy computed from entropy-regularized MDPs, which do not employ the observation function.

6 Conclusion and FutureWork

In this paper, we introduce information-theoretic definitions of opacity in dynamical systems modeled as Markov decision processes, against observers with imperfect information. Given the constraints on task performance, we develop opacity-enforcement policy gradient methods based on message passing in Hidden Markov Models (HMMs) for two basic types of opacity: last-state opacity and initial-state opacity. We expect the fundamental results on last-state opacity and initial-state opacity would be extended to other types of opacity, including language-based and model-based opacity and other obfuscation methods.

While the algorithm exhibits good performance in experiments, its drawback lies in high computational complexity due to the utilization of the forward-backward algorithm for gradient calculation. Finding alternative approaches to mitigate computation complexity will be among our future steps. Another direction to explore would be to investigate opacityenforcement under different assumptions for the observer, for example, observers with imprecise knowledge about the agent's policy. Lastly, though the objective is to maximize opacity, the same approaches can be used for minimizing opacity, and thus maximizing transparency, which is a desired property for AI and robotic systems interacting with humans. Future work would also look into potential applications and evaluate the effects of transparency in multi-agent teaming.

Acknowledgements

This work was sponsored in part by the Army Research Office and was accomplished under Grant Number W911NF-22-10034 and by the Army Research Laboratory under Cooperative Agreement Number W911NF-22-2-0233, and in part by NSF under grant No. 2144113. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Office, the Army Research Lab, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein."