Cold boot attack is a side channel attack that recovers data from memory, which persists for a short period after power is lost. In the course of this attack, the memory gradually degrades over time and only a corrupted version of the data may be available to the attacker. Recently, great efforts have been devoted to reconstructing the original data from a corrupted version of AES key schedules, based on the assumption that all bits in the charged states tend to decay to the ground states while no bit in the ground state ever inverts. However, in practice, there is a small number of bits flipping in the opposite direction, called reverse flipping errors. In this paper, motivated by the latest work that formulates the relations of AES key bits as a Boolean Satisfiability problem, we move one step further by taking the reverse flipping errors into consideration and employing an off-the-shelf MaxSAT solver to accomplish the key recovery of AES-128 key schedules from decayed memory images. Specifically, a MaxSAT solver takes the relations of key bits as hard constraints and the bits in the charged states as soft constraints, then it tries to satisfy all the hard constraints and as many soft constraints as possible by eliminating the unsatisfied minority. Experimental results show that, in the presence of reverse flipping errors, the MaxSAT approach enables reliable recovery of key schedules with significantly less time, compared with the SAT approach that relies on brute force search to find out the target errors.

Totalizer (TO) by Bailleux et al. and Half Sorting Network (HS) by Asin et al. are typical CNF encoding methods of cardinality constraint. The former is based on unary adder, while the latter is based on odd-even merge. Although TO is inferior to HS in terms of the number of clauses, TO is superior to HS in terms of the number of variables. We propose a new method called Modulo Totalizer (MTO) to overcome the disadvantage of TO. As an application, we have developed a partial MaxSAT solver with MTO. Preliminary experimental results show that our MTO based MaxSAT solver is comparable to or surpass the conventional TO based maxsat solvers.

Coalition Structure Generation (CSG), a main research issue in the domain of coalition games, involves partitioning agents into exhaustive and disjoint coalitions so that the social welfare is optimized. The advent of compact representation schemes, such as marginal contribution networks (MC-nets), promotes the efficiency of solving the CSG problem. In this paper, inspired by the dramatic speed-up of Boolean Satisfiability Problem (SAT) solvers, we make the first step towards a study of applying MaxSAT solvers to the CSG problem. We set out to encode the MC-nets into propositional Boolean logic and utilize an off-the-shelf MaxSAT solver as an optimization tool for solving the CSG problem. Specifically, based on the previous works, we encode rule relations and their constraints into weighted partial MaxSAT formulas and show that MaxSAT solvers are useful in solving the CSG problem. Furthermore, we put forward a brand-new method based on agent relations which specify whether two agents of a rule are in the same coalition. Experimental evaluations show that our methods outperform other state-of-the-art algorithms.

This paper proposes a hybrid particle swarm optimization algorithm for solving Job Shop Scheduling Problems (JSSP) to minimize the maximum makespan. A new hybrid heuristic, based on Particle Swarm Optimization (PSO), Tabu Search (TS) and Simulated Annealing (SA), is presented. PSO combines local search (by self-experience) with global search (by neighboring experience), achieving a high search efficiency. TS uses a memory function to avoid being trapped at a local minimum, and has emerged as an effective algorithmic approach for the JSSP. This method can also be referred to as calculation of the horizontal direction. SA employs certain probability to avoid becoming trapped in a local optimum and the search process can be controlled by the cooling schedule (also known as calculation of vertical direction). By reasonably combining these three different search algorithms, we develop a robust, fast and simply implemented hybrid optimization algorithm HPTS (Hybrid of Particle swarm optimization, Tabu search and Simulated annealing). This hybrid algorithm is applied to the standard benchmark sets and compared with other approaches. The experimental results show that the proposed algorithm could obtain the high-quality solutions within relatively short computation time. For 6 of 43 instances, new upper bounds among the unsolved problems are found in a short time in HPTS.

In Web retrieval, it is often the case that the results given by search engines are not just what we want. To solve this problem there have been many studies on improving queries to be submitted to search engines. However, they are still insufficient due to lack of consideration on time information. To remedy this we propose a user-schedule-based Web page recommendation method. The method makes use of a user's schedule to make the recommendation suite to his/her requests. In addition, an algorithm for extracting related words is introduced as a key technique in this method. Some preliminary experiments show very promising results in recommending Web pages relevant to users requests. We also confirmed that this algorithm outperforms a method using mutual information.

The architecture of a data flow machine, called DFM, is developed for parallel list processing. The DFM can maximally exploit parallelism inherent in list processing, due to its ultra-multi-processing mechanism, packet communication-based parallel and pipeline execution mechanism, and lenient cons mechanism. A practical DFM implementation is described. A DFM prototype machine is implemented and DFM performance is evaluated in a simulation on the register transfer level using several benchmark programs. The DFM single processor system is shown to be about five times faster than conventional machines which use the same device technology, while a multi-processor DFM system is shown to achieve a linear speed-up ratio of 0.6 ~ 0.9.