Tolerant Algebraic Side-Channel Attack (TASCA) is a combination of algebraic and side-channel analysis with error tolerance. Oren et al., used mathematical programming to implement TASCA over a round-limited version o...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
Tolerant Algebraic Side-Channel Attack (TASCA) is a combination of algebraic and side-channel analysis with error tolerance. Oren et al., used mathematical programming to implement TASCA over a round-limited version of AES. In [7], Liu et al. revisited their results and introduced a TASCA-cp model that delivers solutions to this 1-round relaxation with orders of magnitude improvement in both solving time and memory consumption. this paper extends the result and considers TASCA for the full 10-rounds AES algorithm. Two approaches are introduced: staged and integrated. the staged approach uses TASCA-cp as a spring board to enumerate and check its candidate solutions against the requirements of subsequent rounds. the integrated model formulates all the rounds of AES together with side-channel constraints on all rounds within a single unified optimization model. Empirical results shows both approaches are suitable to find the correct key of AES while the integrated model dominates the staged both in simplicity and solving time.
Scheduling a subset of solvers belonging to a given portfolio has proven to be a good strategy when solving constraint Satisfaction Problems (CSPs). In this paper, we show that this approach can also be effective for ...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Scheduling a subset of solvers belonging to a given portfolio has proven to be a good strategy when solving constraint Satisfaction Problems (CSPs). In this paper, we show that this approach can also be effective for constraint Optimization Problems (COPs). Unlike CSPs, sequential execution of optimization solvers can communicate information in the form of bounds to improve the performance of the following solvers. We provide a hybrid and flexible portfolio approach that combines static and dynamic time splitting for solving a given COP. Empirical evaluations show the approach is promising and sometimes even able to outperform the best solver of the porfolio.
Novel search space splitting techniques have recently been successfully exploited to paralleliz constraintprogramming and Mixed Integer programming solvers. We first show how universal hashing can be used to extend o...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Novel search space splitting techniques have recently been successfully exploited to paralleliz constraintprogramming and Mixed Integer programming solvers. We first show how universal hashing can be used to extend one such interesting approach to a generalized setting that goes beyond discrepancy-based search, while still retaining strong theoretical guarantees. We then explain that such static or explicit splitting approaches are not as effective in the context of parallel combinatorial search with intensive knowledge acquisition and sharing such as parallel SAT, where implicit splitting through clause sharing appears to dominate. Furthermore, we show that in a parallel setting there exists a surprising tradeoff between the well-known communication cost for knowledge sharing across multiple compute nodes and the so far neglected cost incurred by the computational load per node. We provide experimental evidence that one can successfully exploit this tradeoff and achieve reasonable speedups in parallel SAT solving beyond 16 cores.
In this paper we present new techniques for improving backtracking based Quantified constraint Satisfaction Problem (QCSP) solvers. QCSP is a generalization of CSP in which variables are either universally or existent...
详细信息
ISBN:
(纸本)9783540749691
In this paper we present new techniques for improving backtracking based Quantified constraint Satisfaction Problem (QCSP) solvers. QCSP is a generalization of CSP in which variables are either universally or existentially quantified and these quantifiers can be alternated in arbitrary ways. Our main new technique is solution directed backjumping (SBJ). In analogue to conflict directed backjumping, SBJ allows the solver to backtrack out of solved sub-trees without having to find all of the distinct solutions normally required to validate the universal variables. Experiments withthe solver QCSP-Solve demonstrate that SBJ can improve its performance on random instances by orders of magnitude. In addition to this contribution, we demonstrate that performing varying levels of propagation for universal vs. existential variables can also be useful for enhancing performance. Finally, we discuss some techniques that are technically interesting but do not yet yield empirical improvements.
Binarized Neural Networks (BNNs) are an important class of neural network characterized by weights and activations restricted to the set {-1, +1}. BNNs provide simple compact descriptions and as such have a wide range...
详细信息
ISBN:
(纸本)9783030300487
Binarized Neural Networks (BNNs) are an important class of neural network characterized by weights and activations restricted to the set {-1, +1}. BNNs provide simple compact descriptions and as such have a wide range of applications in low-power devices. In this paper, we investigate a model-based approach to training BNNs using constraintprogramming (cp), mixed-integer programming (MIP), and cp/MIP hybrids. We formulate the training problem as finding a set of weights that correctly classify the training set instances while optimizing objective functions that have been proposed in the literature as proxies for generalizability. Our experimental results on the MNIST digit recognition dataset suggest that-when training data is limited-the BNNs found by our hybrid approach generalize better than those obtained from a state-of-the-art gradient descent method. More broadly, this work enables the analysis of neural network performance based on the availability of optimal solutions and optimality bounds.
the necessity of non-binary constraint satisfaction algorithms is increasing because many real problems are inherently non-binary. Considering overconstrained problems (and Partial Forward Checking as the solving algo...
详细信息
In this paper we argue that an attractive and potentially very general way of achieving generalized are consistency (GAC) on a constraint is by using unit propagation (UP) over a CNF encoding of the constraint. this a...
详细信息
ISBN:
(纸本)9783540749691
In this paper we argue that an attractive and potentially very general way of achieving generalized are consistency (GAC) on a constraint is by using unit propagation (UP) over a CNF encoding of the constraint. this approach to GAC offers a number of advantages over traditional constraint specific algorithms (propagators): it is easier to implement, it automatically provides incrementality and decrementality in a backtracking context, and it can provide clausal reasons to support learning and non-chronological backtracking. Although UP on standard CNF encodings of a constraint fails to achieve GAC, we show here that alternate CNF encodings can be used on which UP does achieve GAC. We provide a generic encoding applicable to any constraint. We also give structure specific encodings for the regular, among, and gen-sequence constraints on which UP can achieve GAC withthe same run time bounds as previously presented propagators. Finally, we explain how a UP engine can be added to a CSP solver to achieve a seamless integration of constraints encoded in CNF and propagated via UP and those propagated via traditional constraint specific propagators.
Computing lower bounds to the best-cost extension of a tuple is an ubiquous task in constraint optimization. A particular case of special interest is the computation of lower bounds to all singleton tuples, since it p...
详细信息
constraintprogramming (cp) is a very general programming paradigm that proved its efficiency on solving complex industrial problems. Most real-life problems are stochastic in nature, which is usually taken into accou...
详细信息
When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max? Should one implement linear equations both with and without coefficients? Constrai...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max? Should one implement linear equations both with and without coefficients? constraint variants are ubiquitous: implementing them requires considerable effort, but yields better performance. this abstract shows how to use views to derive propagator variants where derived propagators are perfect in that they inherit essential properties such as correctness and domain and bounds consistency. Techniques for systematically deriving propagators are developed, and the abstract sketches an implementation architecture for views that is independent of the underlying constraintprogramming system. Evaluation of views implemented in Gecode shows that derived propagators are efficient and that views often incur no overhead. Views have proven essential for implementing Gecode, substantially reducing the amount of code that needs to be written and maintained.
暂无评论