L’intérêt des différents langages de la famille des diagrammes de décisionvalués (VDD) est qu’ils admettent des algorithmes en temps polynomialpour des traitements (comme l’optimisation, la cohérence inverse globale,l’inférence) qui ne sont pas polynomiaux (sous l’hypothèse P 6= NP), si ilssont effectués sur le problème dans sa forme originale tel que les réseaux decontraintes ou les réseaux bayésiens.Dans cette thèse, nous nous intéressons au problème de configuration deproduit, et plus spécifiquement, la configuration en ligne avec fonction de valuationassociée (typiquement, un prix). Ici, la présence d’un utilisateur enligne nous impose une réponse rapide à ses requêtes, rapidité rendant impossiblel’utilisation de langages n’admettant pas d’algorithmes en temps polynomialpour ces requêtes. La solution proposée est de compiler hors-ligneces problèmes vers des langages satisfaisant ces requêtes, afin de diminuer letemps de réponse pour l’utilisateur.Une première partie de cette thèse est consacrée à l’étude théorique desVDD, et plus particulièrement les trois langages Algebraic Decision Diagrams,Semi ring Labelled Decision Diagrams et Affine Algebraic Decision Diagrams(ADD, SLDD et AADD). Nous y remanions le cadre de définition des SLDD,proposons des procédures de traductions entre ces langages, et étudions la compacitéthéorique de ces langages. Nous établissons dans une deuxième partie lacarte de compilation de ces langages, dans laquelle nous déterminons la complexitéalgorithmique d’un ensemble de requêtes et transformations correspondantà nos besoins. Nous proposons également un algorithme de compilationà approche ascendante, ainsi que plusieurs heuristiques d’ordonnancement devariables et contraintes visant à minimiser la taille de la représentation aprèscompilation ainsi que le temps de compilation. Enfin la dernière partie estconsacrée à l’étude expérimentale de la compilation et de l’utilisation de formescompilées pour la configuration de produit. Ces expérimentations confirmentl’intérêt de notre approche pour la configuration en ligne de produit.Nous avons implémenté au cours de cette thèse un compilateur (le compilateurSALADD) pleinement fonctionnel, réalisant la compilation de réseauxde contraintes et de réseaux bayésiens, et avons développés un ensemble defonctions adaptées à la configuration de produit. Le bon fonctionnement etles bonnes performances de ce compilateur ont été validés via un protocole devalidation commun à plusieurs solveurs. / The different languages from the valued decision diagrams (VDD) family benefitfrom polynomial-time algorithms for some tasks of interest (such as optimization,global inverse consistency, inference) for which no polynomial-timealgorithm exists (unless P = NP) when the input is a constraint network ora Bayesian network considered at start.In this thesis, we focus on configuration product problems, and more specificallyon-line configuration with an associated valuation function (typically, aprice). In this case, the existence of an on-line user forces us to quickly answerto his requests, making impossible the use of languages that does not admitpolynomial-time algorithm for this requests. Therefore, our solution consistsin an off-line compilation of these problems into languages that admit suchpolynomial-time algorithms, and thus decreasing the latency for the user.The first part of this thesis is dedicated to the theoretical study of VDDs,an more specifically Algebraic Decision Diagrams (ADDs), Semi ring LabelledDecision Diagrams (SLDDs) and Affine Algebraic Decision Diagrams(AADDs). We revisit the SLDD framework, propose translation proceduresbetween these languages and study the succinctness of these languages. In asecond part, we establish a knowledge compilation map of these languages,in which we determine the complexity of requests and transformations correspondingto our needs. We also propose a bottom-up compilation algorithmand several variables and constraints ordering heuristics whose aim is to reducethe size of the compiled form, and the compilation time. The last partis an experimental study of the compilation and the use of the compiled formin product configuration. These experimentations confirm the interest of ourapproach for on-line product configuration.We also implemented a fully functional bottom-up compiler (the SALADDcompiler), which is capable of compiling constraints network and Bayesian networkinto SLDDs. We also developed a set of functions dedicated to productconfiguration. The proper functioning and good performances of this programwas validated by a validation protocol common to several solvers.

[pt] Diagramas de decisão são uma generalização de árvores de decisão, já propostos como um modelo de aprendizado de máquina para classificação supervisionada mas não largamente adotados. A razão é a dificuldade em treinar o modelo, já que o requerimento de decidir splits (partições) e merges (uniões de nós) em conjunto pode levar a problemas difíceis de otimização combinatória. Um diagrama de decisão tem importantes vantagens sobre árvores de decisão, pois melhor expressa conceitos binários disjuntos, evitando o problema de duplicação de subárvores e, portanto, apresentando menos fragmentação em nós internos. Por esse motivo, desenvolver algoritmos efetivos de construção é um esforço importante. Nesse contexto, o algoritmo Optimal Decision Diagram (ODD) foi recentemente proposto, formulando a construção do diagrama com programação inteira mista (MILP na sigla em inglês), com um warm start proveniente de uma heurística construtiva gulosa. Experimentos mostraram que essa heurística poderia ser aperfeiçoada, a fim de encontrar soluções próximas do ótimo de maneira mais efetiva, e por sua vez prover um warm start melhor. Nesse estudo, reportamos aperfeiçoamentos para essa heurística construtiva, sendo eles a randomização das decisões de split, a poda de fluxos puros (ou seja, fluxos de exemplos pertencentes a uma única classe), e aplicando uma poda bottom-up (de baixo para cima), que considera a complexidade do modelo além da sua acurácia. Todos os aperfeiçoamentos propostos têm efeitos positivos na acurácia e generalização, assim como no valor objetivo do algoritmo ODD. A poda bottom-up, em especial, tem impacto significativo no valor objetivo, e portanto na capacidade da formulação MILP de encontrar soluções ótimas. Ademais, provemos experimentos sobre a expressividade de diagramas de decisão em comparação a árvores no contexto de pequenas funções booleanas em Forma Normal Disjuntiva (DNF na sigla em inglês), assim como uma aplicação web para a exploração visual dos métodos construtivos propostos. / [en] Decision diagrams are a generalization of decision trees. They have been repeatedly proposed as a supervised classification model for machine learning but have not been widely adopted. The reason appears to be the difficulty of training the model, as the requirement of deciding splits and merging nodes can lead to difficult combinatorial optimization problems. A decision diagram has marked advantages over decision trees because it better models disjoint binary concepts, avoiding the replication of subtrees and thus has less sample fragmentation in internal nodes. Because of this, devising an effective construction algorithm is important. In this context, the Optimal Decision Diagram (ODD) algorithm was recently proposed, which formulates the problem of building a diagram as a mixed-integer linear program (MILP), with a warm start provided by a greedy constructive heuristic. Initial experiments have shown that this heuristic can be improved upon, in order to find close-to-optimal solutions more effectively and in turn provide the MILP with a better warm start. In this study, we report improvements to this constructive heuristic, by randomizing the split decisions, pruning pure flows (i.e. flows with samples from a single class), and applying bottom-up pruning, which considers the complexity of the model in addition to its accuracy. All proposed improvements have positive effects on accuracy and generalization, as well as the objective value of the ODD algorithm. The bottom-up pruning strategy, in particular, has a substantial impact on the objective value, and thus on the ability of the MILP solver to find optimal solutions. In addition, we provide experiments on the expressiveness of decision diagrams when compared to trees in the context of small boolean functions in Disjoint Normal Form (DNF), as well as a web application for the visual exploration of the proposed constructive approaches.

Sistemų gedimo modeliavimas paprastai vykdomas taikant taip vadinamus gedimų medžius. Sistemos gedimo tikimybės ir gedimo atsiradimo priežasčių vertinimas dažniausiai atliekamas sudarant minimalių kirtimų aibę (MCS) ir pagal ją įvertinant gedimo tikimybę. Pastaruosius dvidešimt metų tiksliam gedimo tikimybės vertinimui yra taikoma dvejetainė sprendimų diagrama (BDD). Tačiau BDD sudarymo ir taikymo metodika vis dar yra tobulinama. Iki šiol Lietuvoje sistemos gedimo tikimybės vertinimui BDD dar nebuvo taikyta. Pristatant atliktą darbą aprašomi pagrindiniai MCS ir BDD sudarymo metodai bei jų taikymo ypatybės. Taip pat pateikiamas Kauno hidroelektrinės užtvankos vartų valdymo sistemos gedimo modelis ir gedimo tikimybės vertinimas. Šiuo tikslu buvo taikomi skirtingi MCS ir BDD sudarymo metodai bei atitinkamos programinės priemonės. Atlikus bandomuosius skaičiavimus taip pat pateikiamas gautų rezultatų palyginimas. Darbe apibūdinami pagrindiniai MCS ir BDD taikymo privalumai ir trūkumai bei pristatoma naujai sukurta programinė priemonė „DemoITE“. Taikant išanalizuotus algoritmus bei sukurtą programinę priemonę „DemoITE“ buvo ištirtos ir nustatytos sistemos gedimo priežastys bei tiksliai įvertinta sistemos gedimo tikimybė. Be to, pasiūlyta bazinių įvykių rangavimo principas, įgalinantis gauti mažiausią BDD struktūrą. / Modelling of system failure usually is performed applying so-called fault trees. Assessment of system failure probability and failure occurrence causes usually is performed developing a minimal cut-set (MCS) and according to it evaluating probability of system failure. The last twenty years a binary decision diagram (BDD) has been applied for the exact evaluation of system failure. However, a methodology of creation and application of BDD is still under development. Till now in Lithuania for the assessment of system failure probability BDD has not been applied yet. Presenting a performed work the main methods of development of MCS and BDD as well as features of their application is described. Also, the model and assessment of failure of Kaunas hydropower dam gates’ control system is presented. For this task the different methods of development of MCS and BDD as well as corresponding software was applied. Having performed the testing calculations a comparison of results is presented too. In the work the main advantages and disadvantages of MCS and BDD application are described and newly created software “DemoITE” is introduced. The developed algorithms and universal software “DemoITE” is used for visualization of failure causes and for exact estimation of the investigated system failure probability. Also, it is proposed the order of basic events on purpose to design the least BDD.

Binary Decision Diagrams (BDDs) sind eine Datenstruktur für Boolesche Funktionen, die auch unter dem Namen branching program bekannt ist. In ordered binary decision diagrams (OBDDs) müssen die Tests einer festen Variablenordnung genügen. In free binary decision diagrams (FBDDs) darf jede Variable höchstens einmal getestet werden. Die Effizienz neuer Varianten des BDD-Konzepts wird gewöhnlich anhand spektakulärer (worst-case) Beispiele aufgezeigt. Wir verfolgen einen anderen Ansatz und vergleichen die Darstellungsgrößen für fast alle Booleschen Funktionen. Während I. Wegener bewiesen hat, daß für die `meisten' n die erwartete OBDD-Größe einer zufälligen Booleschen Funktion von n Variablen gleich der worst-case Größe bis auf Terme kleinerer Ordnung ist, zeigen wir daß dies nicht der Fall ist für n innerhalb von Intervallen konstanter Länge um die Werte n = 2h + h. Ferner gibt es Bereiche von n, in denen minimale FBDDs fast immer um mindestens einen konstanten Faktor kleiner sind als minimale OBDDs. Unsere Hauptsätze ha ben doppelt exponentielle Wahrschein- lichkeitsschranken (in n). Außerdem untersuchen wir die Entwicklung zufälliger OBDDs und ihrer worst-case Größe und decken dabei ein oszillierendes Verhalten auf, das erklärt, warum gewisse Aussagen im allgemeinen nicht verstärkt werden können. / Binary Decision Diagrams (BDDs) are a data structure for Boolean functions which are also known as branching programs. In ordered binary decision diagrams (OBDDs), the tests have to obey a fixed variable ordering. In free binary decision diagrams (FBDDs), each variable can be tested at most once. The efficiency of new variants of the BDD concept is usually demonstrated with spectacular (worst-case) examples. We pursue another approach and compare the representation sizes of almost all Boolean functions. Whereas I. Wegener proved that for `most' values of n the expected OBDD size of a random Boolean function of n variables is equal to the worst-case size up to terms of lower order, we show that this is not the case for n within intervals of constant length around the values n = 2h + h. Furthermore, ranges of n exist for which minimal FBDDs are almost always at least a constant factor smaller than minimal OBDDs. Our main theorems have doubly exponentially small probability bounds (in n). We also investigate the evolution of random OBDDs and their worst-case size, revealing an oscillating behaviour that explains why certain results cannot be improved in general.

abstract: Access control is necessary for information assurance in many of today's applications such as banking and electronic health record. Access control breaches are critical security problems that can result from unintended and improper implementation of security policies. Security testing can help identify security vulnerabilities early and avoid unexpected expensive cost in handling breaches for security architects and security engineers. The process of security testing which involves creating tests that effectively examine vulnerabilities is a challenging task. Role-Based Access Control (RBAC) has been widely adopted to support fine-grained access control. However, in practice, due to its complexity including role management, role hierarchy with hundreds of roles, and their associated privileges and users, systematically testing RBAC systems is crucial to ensure the security in various domains ranging from cyber-infrastructure to mission-critical applications. In this thesis, we introduce i) a security testing technique for RBAC systems considering the principle of maximum privileges, the structure of the role hierarchy, and a new security test coverage criterion; ii) a MTBDD (Multi-Terminal Binary Decision Diagram) based representation of RBAC security policy including RHMTBDD (Role Hierarchy MTBDD) to efficiently generate effective positive and negative security test cases; and iii) a security testing framework which takes an XACML-based RBAC security policy as an input, parses it into a RHMTBDD representation and then generates positive and negative test cases. We also demonstrate the efficacy of our approach through case studies. / Dissertation/Thesis / M.S. Computer Science 2014

[pt] A Gestão de Estoque eficiente permeia a escolha do método de controle mais adequado, principalmente em empresas que apresentem grande variedade de itens em estoque, quando a definição de métodos diferentes para cada item pode resultar em ganhos pela redução de excessos ou faltas, assim como pela redução de custos administrativos dessa gestão. A empresa estudada se insere nesse contexto, pois apresenta excesso de materiais em estoque, bem como faltas de alguns itens, gerando prejuízos financeiros decorrentes da má gestão de seu estoque. Assim, por adotar a mesma política de controle de estoque para todos os itens, que abrangem de materiais de administração predial a equipamentos de exploração de petróleo e gás, essa empresa se depara com a necessidade de implementar controles de estoque mais adequados para cada um desses itens. Desse modo, este trabalho propõe responder a seguinte pergunta-chave de estudo: Qual a política de gestão de estoques mais adequada para cada produto analisado? Para responder a essa pergunta, o trabalho propõe a elaboração de um Diagrama de Decisão que auxilie na tomada dessa decisão. Para tanto, busca classificar esses SKU quanto a Curva ABC para valor (RS), volume consumido e criticidade, sendo esta última definida com apoio do Analytic Hierarchy Process (AHP). Além disso, analisa as distribuições de demanda e de lead time de cada SKU como parâmetros para auxiliar nessa decisão, formando um diagrama onde os nós representam esses parâmetros (Curva ABC, Demanda e Lead Time) e os caminhos correspondem as classificações internas de cada um desse parâmetros, apontando, ao final de cada caminho, qual o melhor controle de estoque para o SKU analisado considerando o Kanban e o MRP como alternativas. Aplicou-se a Design Science Research (DSR) como método de estudo. Com a aplicação desse método pretende-se que o Diagrama proposto seja um artefato capaz de atender as diferentes áreas de negócio da empresa, contribuindo para disseminação de uma ferramenta padrão para a tomada de decisão quanto ao método de controle de estoque a ser empregado para cada SKU. Assim, espera-se que o artefato proposto posso contribuir com todas as áreas da empresa, ampliando o conhecimento gerado na área de negócio delimitada para este estudo. Por fim, o trabalho contribuiu com o desenvolvimento de uma ferramenta capaz de atender as necessidades da empresa quanto a adoção de diferentes métodos de controle de estoques, indiferentemente da área de negócio a qual se aplica. Além disso, na área delimitada para implementação deste estudo, a aplicação desse diagrama obteve a redução do excesso e das faltas para os SKU analisados, bem como apresentou forte potencial de redução de custos administrativos em função da possibilidade de adotar métodos mais simples de controle de estoque para alguns itens. / [en] Efficient Inventory Management permeates the choice of the most appropriate control method, especially in companies that have a wide variety of items in stock, when the definition of different methods for each item can result in gains by reducing excesses or shortages, as well as by reduction of administrative costs of this management. The studied company is part of this context, as it presents an excess of materials in stock, as well as shortages of some items, generating financial losses resulting from the mismanagement of its stock. Thus, by adopting the same inventory control policy for all items, which range from building management materials to oil and gas exploration equipment, this company is faced with the need to implement more adequate inventory controls for each of these tems. Thus, this paper proposes to answer the following key study question: What is the most adequate inventory management policy for each product analyzed? To answer this question, this work proposes the elaboration of a Decision Diagram that helps in making that decision. Therefore, it seeks to classify these SKU as the ABC Curve for value (Rs), volume consumed and criticality, the latter being defined with the support of the Analytic Hierarchy Process (AHP). In addition, it analyzes the demand and lead time distributions of each SKU as parameters to assist in this decision, forming a diagram where the nodes represent these parameters (ABC curve, Demand and Lead Time) and the paths correspond to the internal classifications of each one of these parameters, pointing, at the end of each path, which is the best stock control for the SKU analyzed considering Kanban and MRP as alternatives. Design Science Research (DSR) was applied as a study method. With the application of this method, the proposed Diagram is intended to be an artifact capable of serving the different business areas of the company, contributing to the dissemination of a standard tool for decision making regarding the inventory control method to be employed for each SKU. Thus, it is expected that the proposed artifact can contribute to all areas of the company, expanding. Finally, the work contributed to the development of a tool capable of meeting the company s needs regarding the adoption of different inventory control methods, regardless of the business area to which it applies. In addition, in the area defined for the implementation of this study, the application of this diagram obtained the reduction of excess and shortages for the SKUs analyzed, as well as presenting a strong potential for reducing administrative costs due to the possibility of adopting simpler methods of controlling stock for some items.