-This paper discusses the security issues in data driven coordination languages. These languages rely on a data space shared by the agents and used to coordinate their activities. We extend these languages with a main distinguishing feature, which is the possibility to define fine-grained security conditions, associated with every datum in the shared space. Two main ideas makes it possible: the consideration of an abstraction of agents' states in the form of data at language level and the introduction of a richer interaction mechanism than state-of-the-art templates. This novel security mechanism allows both agents and system designers to prohibit undesirable interactions.
When designing logically distributed applications and open
Multi-Agent Systems (MAS), developing applications without
knowing either the overall structure of the system or the
agents that will be functioning in it is a challenge. Data driven
coordination languages, with the pioneer language Linda [
Relying on a shared space for agent interaction naturally
handles open systems design [
In data driven coordination languages, security is generally
enforced by using multiple (logical) spaces or by stating
“Interaction Laws”. With multiple spaces (e.g. Klaim [
We would like to equip data driven coordination languages with a security mechanism that allows for the protection of the exchanged data in a fine-grained way. We want to let agents specify, when they add a datum to the data space, the conditions under which it can be read or taken by others. We also would like the designer of the system to specify the conditions under which an agent can or cannot add a certain datum to the space, following the application logic. To do so, we perform several modifications of the shared space model, and propose a new language, called LACIOS (Language for Agent Contextual Interaction in Open Systems), which is the linguistic embodiment of the modified model.
In [
The remainder of this paper is structured as follows. We give an overview of LACIOS in section II. Section III gives the basic syntax of our language; Section IV addresses the security issue, and section V provides the complete specification of agents’ behaviors. Section VI presents the programming language JAVA-LACIOS. The proposal is discussed with respect to the state of the art in section VII before concluding with further lines of research.
The agents that are defined in a LACIOS program are usually the local agents. The users, external agents and external systems that are represented by an agent in the MAS are not modeled, only their actions are observed in the MAS, through the nondeterministic behavior of the local agent. An agent in LACIOS is then an entity, that has a state, a local memory and a nondeterministic behavior. As we will define it later, the whole behavior of the agent is not defined in LACIOS.
An agent can have a complex behavior, by using additional operators, besides the standard operations defined in LACIOS.
A MAS written in LACIOS is defined by a dynamic set of agents interacting with an environment, which is composed of a dynamic set of objects. To illustrate the syntax of LACIOS, an example application is used throughout the paper. In this example, human travelers are in a train station in which schedules, booking, payment services and information sources coexist. Two agent types are considered in here: Traveler agents represent travelers wishing to make a journey and Train agents represent trains, and generate information concerning future departures, arrivals, delays, etc. All these agents interact by exchanging data via a shared space in the same way as for all data driven coordination models.
A MAS written in LACIOS is an open system in two ways.
As for every data driven language, agents in LACIOS can
join and leave the system freely. In addition, external - non
modeled - systems and users can interact with the MAS. As
we will define it later, users (e.g. travelers) interact with the
MAS by instantiating the values of certain variables in the
code of the agents that represent them. External systems (e.g.
trains) can interact with the MAS by instantiating variables III. BASIC SYNTAX AND INFORMAL SEMANTICS FOR
with values as well. They can also execute agents that interact Lacios
with the MAS Environment directly. The figure 1 illustrates LACIOS is a data driven language for the design and
the MAS architecture. The modeled MAS executes on a host, implementation of open and secure MAS. For the specification
where (local) agents add, read and take objects to/from the of agent behavior, four primitives inspired by Linda and a
MAS environment. Every agent is either independent (like set of operators borrowed from Milner’s CCS [
Definition 1 (Agent): An agent is a computer system capable of autonomous action in some environment in order to meet its design objectives.
From the security point of view, LACIOS has two objectives: 1) to support a global control by the environment of the insertion by the agents of objects in order to ensure that the new objects are not fraudulent (authenticity, availability), 2) to support a local control by the agents that can specify who can access the object that they add to the environment in order to ensure their privacy (authenticity, confidentiality and availability). To do so, agents have to have a state defining who they are. This is the first modification we perform to the original model: the consideration of an abstraction of agents’ states in the form of data at language level. These states are defined as a set of property value pairs (e.g. fidentif ier 10; position node1g). Agents’ states in LACIOS are data representing the state of the agents that are accessed by the environment only for matching and security purposes (they are not directly accessible by the other agents). which is composed of a dynamic set of objects. Figure 2 illustrates the general principle of LACIOS. Agents are defined by a behavior (a process), a state (data) and a local memory in which they store the objects they perceive or retrieve from the environment. Agents can perceive (read only) and/or retrieve (read and take) objects from the environment. First the four primitives of LACIOS will be presented; their parameters will be defined along with the details of the language.
::= spawn j add j update j look
The primitive spawn launches a new agent and provides it with an initial state and a behavior. An add action adds an object to the environment. The update primitive changes locally the old values of the agent’s state to the new ones.
Unlike traditional retrieval primitives, the look primitive enables agents for both the perception and retrieval of objects as will be described below. The primitive looks for objects in the environment that satisfy the agents’ conditions expressed as parameters. Agents can use their own states in the parameter expression of a look, which are accessible by the environment only, when the parameter expression is evaluated. Note that, the state of an agent cannot be accessed directly by the other agents (through a look expression). In order to be observable to the others, an agent has to add an object representing itself to the environment autonomously (as in Fig. 2, where the agent decides not to publish a part of its state). Having data representing agents in the environment allows the agents of the system to discover each other by simply interrogating the environment a` la Linda.
Remark 1: We assume the existence of the boolean type in the language, i.e. 9i 2 f1; : : : ; nbtg; typei = ftrue; false; nilg
Notation 1: We denote the set of values supported by the
nbt language as T = [ typei.
i=1
Definition 3 (Property): N is the property space, and is a countable set of properties. A property 2 N is defined by a type type( ) 2 ftype1; : : : ; typenbtg.
The value nil has a twofold use in the syntax of LACIOS.
First, it represents every semantic error in a program. When a semantic error is encountered, the corresponding expression is set at nil. Second, a property whose value is equal to nil is considered as undefined (as if it is nonexistent), and is usually omitted.
Notation 2: We note unknown a value of the type type( ) that is defined but doesn’t have a value. For instance, unknowndestination is a value of the same type as the property destination, whose value is (temporarily) unknown.
A description is composed of properties and their corresponding values.
A description is a function that maps properties to values, i.e. d f v j v 2 type( )g 2N . The mapping is omitted when v = nil. We use d( ) in order to access the value v . For each description, the set of properties f j d( ) 6= nilg is finite.
In LACIOS, each description is associated with an entity, which can be an object or an agent. Objects are defined by their descriptions (O is the set of objects), while each agent is defined by a description (their state), a behavior and a local memory (A is the set of agents).
For instance, let o1 be an object representing a traveler, do1 could be defined as follows: fid \o1"; destination \London"; origin \P aris"g. In this example, do1 (origin) is equal to \P aris".
Definition 5 (Entities): = A [ O is the set of entities of the MAS. Each entity ! 2 has a description as defined above denoted by d!. The value of the property of the entity ! is denoted by d!( ).
Remark 2: We assume the existence of the type reference in LACIOS, a value of the type reference designates an entity in , i.e. 9i 2 f1; : : : ; nbtg; typei = [ fnilg.
Expressions are built with values, properties and operators, and are used by agents to describe the data they handle, either A. Data structure locally or to interact with the environment.
For LACIOS, we define a standard information system data Definition 6 (Operators): Each operator op of the language structure: every item of data in the system has a description, is defined by: i.e. a set of property value pairs, and all the properties of (i) arity(op) The number of parameters of the operator, the language are typed. The notions of type, property and (ii) par(op) : f1; : : : ;arity(op)g ! f1; : : : ; nbtg, description are defined as follows. par(op)(i) gives the index of the type of the ith param
Definition 2 (Types): The types of the language are defined eter of the operator op, as type1; : : : ; typenbt. Every typei is a set such that 8(i; j) 2 (iii) ret(op) 2 f1; : : : ; nbtg, the index of the type of the f1; : : : ; nbtg2; i 6= j; typei \ typej = fnilg value resulting from the evaluation of op. For instance, let type1 boolean. The operator and is defined as follows: arity(and) = 2, par(and)(1) = par(and)(2) = 1 and ret(and) = 1.
Besides basic operators, additional operators can be defined by the programmer, specifying complex agents’ processes.
LACIOS is then used mainly for coordination purposes, while the computational model remains non modeled.
An expression may simply be a value, an operator, or a property. For instance, destination 6= \P aris" is a (boolean) expression. If an expression is a property, it refers to a property of the agent that is evaluating it. For instance, when destination appears in the behavior of agent a as in the example above, it designates the destination of a. If a property companion of agent a is of the type reference, companion:destination designates the destination of the companion of a.
An expression e 2 Exp is generated via the grammar found in Table I.
e ::= nil j v , with v 2 T nnil j , with 2 N j op(e; : : : ; e) , with op an operator of the language,
and nil doesn’t appear in any e j :e , with 2 N and type( ) =
In a description, an agent can associate an expression with a property, instead of a value. The result is a symbolic description which is transformed into a description when its associated expressions are evaluated.
symbolic descriptions. A symbolic description sds 2 SDS is a description that maps properties to expressions e , i.e. sds f e j type(e ) = type( )g 2N .
Below is the definition of the add and update primitives, together with their symbolic descriptions parameters.
::= : : : j add(sds) j update(sds)
In order to add an object, an agent executes add(sds), and an object whose description is the evaluation of sds is added to ENV . For instance, add(fticketid ticket:id; price ticket:price + 20; owner idg) adds an object to the environment whose owner is equal to the id of the calling agent, ticketid is equal to the property id of an object in the memory of the calling agent, referred to by the property ticket, and whose price is 20 more than the price paid by the agent. The primitive update(sds) updates a set of properties of the agent with the evaluation of the expressions in sds. When update(sds) is executed, the value of every property in sds becomes equal to the evaluation of the corresponding expression e . For instance, if an agent a executes update(fbudget budget 20; destination \Budapest"g), its budget is decreased by 20 and its destination becomes “Budapest”.
Since we consider a data structure richer than tuples, we also use a matching mechanism richer than templates. To do so, the expressions’ syntax is enhanced with variables, which designate objects not known by the agent, but which will be discovered during the matching process and will be replaced by objects from the environment before their evaluation. Below is the definition of a variable.
Definition 9 (Variables): X is the set of variables. A variable x 2 X is defined by its type type(x) 2 ftype1; : : : ; typenbtg.
The syntax of an expression becomes:
e ::= : : : j x:e with x 2 X ^ type(x) =
For instance, consider the following boolean expression e: t:destination = \London" ^ t:price budget. In this boolean expression, t designates an object, unknown for the moment, where the property destination of t has to be “London” and the price has to be less than the budget of the agent for the expression to be evaluated to true. In this case, the agent executing look with e as a parameter will perceive or retrieve the object.
We can now provide the complete definition of the primitive look.
::= : : : j look(sdsp; sdsr; e)
We choose to use a single primitive to access the environment. The primitive look(sdsp; sdsr; e), with sdsp and sdsr symbolic descriptions, allows both object perception and retrieval (perception and removal from ENV ). It blocks until a set of objects C becomes present in ENV such that the expression e is evaluated to true. When an agent executes look(sdsp; sdsr; e), the set of objects of the environment C is selected for matching with e (each variable is unified with an object from C). The expression e has to be evaluated to true with this unification for look to be executed. The objects associated with the variables in sdsp are perceived and those associated with the variables in sdsr are retrieved. For instance, the following instruction: look(ftrain trg; fticket tkg; tr:destination = \London" ^ tk:price budget ^ tk:train = tr:id) looks for two objects that will be unified with tk and tr. The object associated with tr will be perceived while the object associated with tk will be retrieved. After this instruction has been executed, the two objects will be present in the local memory of the caller agent, which will have two additional properties of the type reference: ticket, which refers to the object associated with the variable tk and train, which refers to the object associated with tr. The object unified with tk won’t be present in ENV anymore.
Consider an agent having two properties destination and budget that are unknown before the execution. The values of these properties come from an external system (e.g. a Web server, a GUI, etc). Here is the description of this agent which properties will be defined during execution resulting from their instantiation by an external system: fbudget b; destination dg, where b and d are variables. Only the action of the external system will be observed, i.e. the assignment of values to the variables, while the system itself is not modeled. We enhance the syntax of an expression with free variables as follows:
e ::= : : : j x with x 2 X The introduction of the variables for the interaction with an external system is interesting insofar as it clearly separates the coordination aspect - what the MAS does - from the interaction with an external system aspect - the context in which the MAS is running. Thus, in the description fbudget b; destination dg, regardless of which system is instantiating the variables b and d, the definition of the description and the behavior of the agent remain unchanged.
We have decided to maintain global sharing of the data between all the agents, and not to isolate them in private environments, thus following the original Linda model. However, this choice leads to the same security problems. More precisely, fraudulent data insertion and retrieval could occur and the agents and the system designer cannot prevent them. In LACIOS, the agents are responsible of the objects that they put in the environment. In order to avoid fraudulent use of these objects, the language supports two control levels, a global level for the designer of the system to control the insertion of objects and a local level for the owner of the objects to control how their object will be used.
The designer of the system knows the conditions under which certain insertions of objects are fraudulent and we provide him/her with a global control of agents insertions of objects. A threat to authenticity (when an agent tries to forge a message for example) is an example of such fraudulent insertions. More generally, objects added to the environment might corrupt the coherence of the data according to the application logic (resulting in two agents with the same position, or with a new bid that is lower than the current one, etc.).
Let us consider for instance, the following action: add(ff rom companion2:id; to companion1:id; subject \coalition"g)
This action is fraudulent, since the agent tries to send a message with a different id than its own. Therefore, this first class of threats concerns the security rules that have to be checked when an add is executed. To overcome threats resulting from the fraudulent adding of objects to the environment, the system designer identifies the critical situations and specifies each one using a security rule s (s 2 S; S Exp is the set of security rules of the system). An expression s in S is a boolean expression in which the designer specifies the conditions on the state of the agent executing add and the conditions on the description of the object that it adds. To do so, we add a specific key word that in the syntax of an expression to designate, in a security rule, the object added by the agent.
e ::= : : : j that:e For instance, here is the expression preventing an agent from adding an object that has a property f rom that is different from its own: s that:f rom = id, where id designates the identifier of the agent executing the add and that designates the object added by the agent. When an agent a executes add(ff rom companion2:id; to companion1:id; subject \coalition"g), the security rule specified by the designer is evaluated to false, because d(f rom) 6= da(id), and the operation is canceled.
The agents of the system know best the conditions under which the perception or retrieval of an object they add is fraudulent, and we provide them with local control to manage the observability of their own objects. A confidentiality threat (e.g. the interception by an agent of another’s confidential information or message), or a threat to availability (e.g. the deletion of the agent’s information or message by another agent) are examples of such fraudulent access. We propose to allow agents to define the observability rules - on perception and on retrieval - and to let the environment check that these conditions are respected.
This is done by enabling an agent, when it adds an object, to manage its observability, i.e. to identify the situations where the perception or retrieval of the added object is prohibited. To do so, the syntax of the primitive add is replaced as follows.
::= : : : j add(sds; ep; er) where ep and er are boolean expressions. The expression ep specifies the conditions that an agent has to satisfy to have the right to perceive the object described by sds, and er defines the conditions that an agent has to satisfy to have the right to retrieve it. When an agent executes look(sdsp; sdsr; e), for each object o 2 C (the set of objects selected for matching from the environment) that is unified with a context variable in sdsp, the expression ep associated to o has to be evaluated to true, and for each object o unified with a context variable in sdsr, the expression er associated with o has to be evaluated to true. Otherwise, the action look cannot be executed with this set of objects. When the agent doesn’t want to restrain the perception or the retrieval of the object described by sds, it assigns true to ep or er respectively. For instance, let agent a (let’s say that a’s companion:id = 5) wants to prevent the message it has addressed to its companion to be retrieved by others, and to be perceived by any agent but itself (the key word that has the same semantics here, i.e. it designates the added object): add(ff rom id; to companion:id; subject \coalition"g; id = that:f rom; id = that:to)
Consider an agent b with db(id) = 10 that executes look(freceiver rg; fmessage mg; m:to = r:id ^ r:destination = destination). The agent b is trying to retrieve a message (object unified with m) and to perceive the object representing the agent to which m is addressed (object unified with r), if its destination is equal to its own. Thanks to the conditions associated with the added object, b won’t be able to perceive a’s message. Concretely, any matching that is trying to unify m with a’s message is prohibited by the environment and is not considered.
Note that, in the development of the security management defined above, we only take into account the security between local agents and the environment. By doing so, we make two assumptions. On the one side, the spawn of an agent representing an external system, user or agent, has to be fulfilled following a security protocol to ensure that this is indeed the agent with the claimed identifier. On the other side, we assume that local agents don’t try to change their identifiers with an update throughout the execution of the system, which is easy to check before the execution of the system. Otherwise, they could dupe the global control mechanism.
::= add(sds) j look(sdsp; sdsr; e) j update(sds) j spawn(P; sds)
We are now ready to define processes, which define agent behavior. The primitive spawn(P; sds) launches a new agent that behaves like the process P and whose description is the result of the evaluation of sds (its transformation to a description ds). Below is the definition of a process, which defines agents’ behaviors.
Definition 10 (Process): Given a set of process identifiers def fKigi2I , a process definition is of the form: 8i 2 I; Ki = Pi, where every Pi is generated via the grammar in Table II. evaluated to true, the program P is executed. A program can also be a parallel composition of programs P kQ, i.e. P and Q are executed in parallel. A program can be an invocation of another process whose identifier is the constant Kj , and which behaves like the process defined by Kj . A program may be a process prefixed by an action :P . Actions are the language primitives, as defined earlier. The operator is introduced to link free variables in P . The process X(P ) introduces nondeterminism in the agents’ behaviors. Indeed, behaves like P where every free variable (in X) is nondeterministically linked with a value in its type.
A coordinated MAS is then defined as follows.
Definition 11 (Coordinated MAS): CS = h ; d; ENV ; Si = A ] O is the set of entities, composed of A the set of agents and O the set of objects, – A is the set of agents.
a is the private memory of agent a, a O [ fag, i.e. the agent has access to its own description, proc(a) is the process defining the behavior of a. – O is the set of objects.
ep(o) returns the predicate specifying the perception conditions of o, i.e. which agents can perceive o. er(o) returns the predicate specifying the retrieval conditions of o, d : ! (N ! T ) is the description function of the MAS, each d(!) is an entity description as described before (denoted by d! as well),
O is the set of objects that are in the environ
ENV ment, S Exp is the set of predicates specifying the conditions that have to be verified, in order for an add to be executed.
Processes, ranged over by P; Q; : : : represent the programs of the MAS, and the behavior of its agents. A program can be a terminated process 0 (usually omitted). It can also be a choice expression between programs bbP c + bbP c, where each P is guarded by the evaluation of a boolean expression: when b is
We have defined a language that, following its operational
semantics (cf. [
A JAVA-LACIOS program is a file where both the behaviors
and the initial state of the coordinated MAS are described.
A coordinated MAS is defined by the set of initial agents,
spawned when the program starts, together with the security
rules S. Programmers write their scripts which are parsed and
compiled, generating a Java program. We have proposed a GUI
for JAVA-LACIOS, which displays the ongoing execution, the
current objects in the environment, the current agents’
behaviors that are executed, etc. The Fig. 3 illustrates the execution
with a Dial A Ride system that we have implemented [
In [
The laws in LGI [
Tagged Sets [
In [
The concurrent access to the environment objects with a look necessitates a synchronization of the add and look calls.
However, an agent calling add has not to be blocked until the environment releases the lock. To this end, we define a buffer to which agents can add objects without blocking, while emptying the buffer is synchronized with the look calls.
when a look is called, the environment is locked while it is still looking for a matching, to guarantee that an agent does not access the environment in an incoherent state, and to be sure that a same object is not retrieved by more than one agent.
If no matching is found, the calling process of the agent is blocked. The blocked processes are notified when an object is added to the environment. In this case, the notified process looks for a matching with the only newly added objects.
An update modifies the agent’s properties locally, but it however influences its interaction with the environment.
Indeed, if a look is currently executing, the matching have to be attempted with the current properties of the agent. When the properties of an agent change, and when they concern properties for which an ongoing look has attempted to match, the execution of the look is executed again, and the pending look requests are notified since they might be concerned by the newly changed properties as well.
The investigation of security issues in data driven coordination languages has lead us to propose a modified language allowing for fine-grained protection of exchanged data via the shared space. This paper has defined LACIOS, which can be used to model a large number of applications in which agents join and leave the system freely, where agents interact with external systems, and where security is crucial. Using LACIOS makes it easier for open MAS designers to translate the concepts manipulated by the agents and their interaction needs to LACIOS syntactic constructs, ensuring information security
VII. DISCUSSION AND RELATED WORK and expressing complex constraints. We have demonstrated
Security is generally enforced by using multiple (logical) this usefulness for a complex transportation application in our
spaces, by stating “Interaction Laws” or by defining roles and recent paper [
Our future works include the consideration of specific
cryptographic properties to ensure authenticity. We are also
investigating the addition of time constructs to LACIOS, inspired by
the works of Busi et al. (e.g. [