# Copyright 2014-2015, Tresys Technology, LLC
#
# This file is part of SETools.
#
# SETools is free software: you can redistribute it and/or modify
# it under the terms of the GNU Lesser General Public License as
# published by the Free Software Foundation, either version 2.1 of
# the License, or (at your option) any later version.
#
# SETools is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser General Public
# License along with SETools. If not, see
# <http://www.gnu.org/licenses/>.
#
from itertools import product
from collections import namedtuple
from . import exception
from . import qpol
from . import symbol
truth_table_row = namedtuple("truth_table_row", ["values", "result"])
def boolean_factory(policy, name):
"""Factory function for creating Boolean statement objects."""
if isinstance(name, Boolean):
assert name.policy == policy
return name
elif isinstance(name, qpol.qpol_bool_t):
return Boolean(policy, name)
try:
return Boolean(policy, qpol.qpol_bool_t(policy, str(name)))
except ValueError:
raise exception.InvalidBoolean("{0} is not a valid Boolean".format(name))
def condexpr_factory(policy, name):
"""Factory function for creating conditional expression objects."""
if not isinstance(name, qpol.qpol_cond_t):
raise TypeError("Conditional expressions cannot be looked up.")
return ConditionalExpr(policy, name)
class Boolean(symbol.PolicySymbol):
"""A Boolean."""
@property
def state(self):
"""The default state of the Boolean."""
return bool(self.qpol_symbol.state(self.policy))
def statement(self):
"""The policy statement."""
return "bool {0} {1};".format(self, str(self.state).lower())
class ConditionalExpr(symbol.PolicySymbol):
"""A conditional policy expression."""
_cond_expr_val_to_text = {
qpol.QPOL_COND_EXPR_NOT: "!",
qpol.QPOL_COND_EXPR_OR: "||",
qpol.QPOL_COND_EXPR_AND: "&&",
qpol.QPOL_COND_EXPR_XOR: "^",
qpol.QPOL_COND_EXPR_EQ: "==",
qpol.QPOL_COND_EXPR_NEQ: "!="}
_cond_expr_val_to_precedence = {
qpol.QPOL_COND_EXPR_NOT: 5,
qpol.QPOL_COND_EXPR_OR: 1,
qpol.QPOL_COND_EXPR_AND: 3,
qpol.QPOL_COND_EXPR_XOR: 2,
qpol.QPOL_COND_EXPR_EQ: 4,
qpol.QPOL_COND_EXPR_NEQ: 4}
def __contains__(self, other):
for expr_node in self.qpol_symbol.expr_node_iter(self.policy):
expr_node_type = expr_node.expr_type(self.policy)
if expr_node_type == qpol.QPOL_COND_EXPR_BOOL and other == \
boolean_factory(self.policy, expr_node.get_boolean(self.policy)):
return True
return False
def __str__(self):
# qpol representation is in postfix notation. This code
# converts it to infix notation. Parentheses are added
# to ensure correct expressions, though they may end up
# being overused. Set previous operator at start to the
# highest precedence (NOT) so if there is a single binary
# operator, no parentheses are output
stack = []
prev_op_precedence = self._cond_expr_val_to_precedence[qpol.QPOL_COND_EXPR_NOT]
for expr_node in self.qpol_symbol.expr_node_iter(self.policy):
expr_node_type = expr_node.expr_type(self.policy)
if expr_node_type == qpol.QPOL_COND_EXPR_BOOL:
# append the boolean name
nodebool = boolean_factory(
self.policy, expr_node.get_boolean(self.policy))
stack.append(str(nodebool))
elif expr_node_type == qpol.QPOL_COND_EXPR_NOT: # unary operator
operand = stack.pop()
operator = self._cond_expr_val_to_text[expr_node_type]
op_precedence = self._cond_expr_val_to_precedence[expr_node_type]
# NOT is the highest precedence, so only need
# parentheses if the operand is a subexpression
if isinstance(operand, list):
subexpr = [operator, "(", operand, ")"]
else:
subexpr = [operator, operand]
stack.append(subexpr)
prev_op_precedence = op_precedence
else:
operand1 = stack.pop()
operand2 = stack.pop()
operator = self._cond_expr_val_to_text[expr_node_type]
op_precedence = self._cond_expr_val_to_precedence[expr_node_type]
if prev_op_precedence > op_precedence:
# if previous operator is of higher precedence
# no parentheses are needed.
subexpr = [operand1, operator, operand2]
else:
subexpr = ["(", operand1, operator, operand2, ")"]
stack.append(subexpr)
prev_op_precedence = op_precedence
return self.__unwind_subexpression(stack)
def __unwind_subexpression(self, expr):
ret = []
# do a string.join on sublists (subexpressions)
for i in expr:
if isinstance(i, list):
ret.append(self.__unwind_subexpression(i))
else:
ret.append(i)
return ' '.join(ret)
@property
def booleans(self):
"""The set of Booleans in the expression."""
bools = set()
for expr_node in self.qpol_symbol.expr_node_iter(self.policy):
expr_node_type = expr_node.expr_type(self.policy)
if expr_node_type == qpol.QPOL_COND_EXPR_BOOL:
bools.add(boolean_factory(self.policy, expr_node.get_boolean(self.policy)))
return bools
def evaluate(self, **kwargs):
"""
Evaluate the expression with the stated boolean values.
Keyword Parameters:
Each keyword parameter name corresponds to a boolean name
in the expression
Return: bool
"""
bools = sorted(self.booleans)
if sorted(kwargs.keys()) != bools:
raise ValueError("Boolean values not set correctly.")
stack = []
for expr_node in self.qpol_symbol.expr_node_iter(self.policy):
expr_node_type = expr_node.expr_type(self.policy)
if expr_node_type == qpol.QPOL_COND_EXPR_BOOL:
nodebool = boolean_factory(self.policy, expr_node.get_boolean(self.policy))
stack.append(kwargs[nodebool])
elif expr_node_type == qpol.QPOL_COND_EXPR_NOT:
operand = stack.pop()
operator = self._cond_expr_val_to_text[expr_node_type]
stack.append(not operand)
else:
operand1 = stack.pop()
operand2 = stack.pop()
operator = self._cond_expr_val_to_text[expr_node_type]
if operator == "||":
stack.append(operand1 or operand2)
elif operator == "&&":
stack.append(operand1 and operand2)
elif operator == "^":
stack.append(operand1 ^ operand2)
elif operator == "==":
stack.append(operand1 == operand2)
else: # not equal
stack.append(operand1 != operand2)
return stack[0]
def truth_table(self):
"""
Generate a truth table for this expression.
Return: list
List item:
tuple: values, result
Tuple item:
values: Dictionary keyed on Boolean names
with each value being T/F.
result: Evaluation result for the expression
given the values.
"""
bools = sorted(str(b) for b in self.booleans)
truth_table = []
# create a list of all combinations of T/F for each Boolean
truth_list = list(product([True, False], repeat=len(bools)))
for row in truth_list:
values = {bools[i]: row[i] for i in range(len(bools))}
truth_table.append(truth_table_row(values, self.evaluate(**values)))
return truth_table
def statement(self):
raise exception.NoStatement