Kenji Hashimoto

Bao Trung Chu, Kenji Hashimoto, Hiroyuki Seki

Quantitative information flow (QIF) is traditionally defined as the expected value of information leakage over all feasible program runs and it fails to identify vulnerable programs where only limited number of runs leak large amount of information. As discussed in Bielova (2016), a good notion for dynamic leakage and an efficient way of computing the leakage are needed. To address this problem, the authors have already proposed two notions for dynamic leakage and a method of quantifying dynamic leakage based on model counting. Inspired by the work of Kawamoto et. al. (2017), this paper proposes two efficient methods for computing dynamic leakage, a compositional method along with the sequential structure of a program and a parallel computation based on the value domain decomposition. For the former, we also investigate both exact and approximated calculations. From the perspective of implementation, we utilize binary decision diagrams (BDDs) and deterministic decomposable negation normal forms (d-DNNFs) to represent Boolean formulas in model counting. Finally, we show experimental results on several examples.

Bao Trung Chu, Kenji Hashimoto, Hiroyuki Seki

A program is non-interferent if it leaks no secret information to an observable output. However, non-interference is too strict in many practical cases and quantitative information flow (QIF) has been proposed and studied in depth. Originally, QIF is defined as the average of leakage amount of secret information over all executions of a program. However, a vulnerable program that has executions leaking the whole secret but has the small average leakage could be considered as secure. This counter-intuition raises a need for a new definition of information leakage of a particular run, i.e., dynamic leakage. As discussed in [5], entropy-based definitions do not work well for quantifying information leakage dynamically; Belief-based definition on the other hand is appropriate for deterministic programs, however, it is not appropriate for probabilistic ones. In this paper, we propose new simple notions of dynamic leakage based on entropy which are compatible with existing QIF definitions for deterministic programs, and yet reasonable for probabilistic programs in the sense of [5]. We also investigated the complexity of computing the proposed dynamic leakage for three classes of Boolean programs. We also implemented a tool for QIF calculation using model counting tools for Boolean formulae. Experimental results on popular benchmarks of QIF research show the flexibility of our framework. Finally, we discuss the improvement of performance and scalability of the proposed method as well as an extension to more general cases.

Martim Brandao, Kenji Hashimoto, Atsuo Takanishi

Trajectory optimization and posture generation are hard problems in robot locomotion, which can be non-convex and have multiple local optima. Progress on these problems is further hindered by a lack of open benchmarks, since comparisons of different solutions are difficult to make. In this paper we introduce a new benchmark for trajectory optimization and posture generation of legged robots, using a pre-defined scenario, robot and constraints, as well as evaluation criteria. We evaluate state-of-the-art trajectory optimization algorithms based on sequential quadratic programming (SQP) on the benchmark, as well as new stochastic and incremental optimization methods borrowed from the large-scale machine learning literature. Interestingly we show that some of these stochastic and incremental methods, which are based on stochastic gradient descent (SGD), achieve higher success rates than SQP on tough initializations. Inspired by this observation we also propose a new incremental variant of SQP which updates only a random subset of the costs and constraints at each iteration. The algorithm is the best performing in both success rate and convergence speed, improving over SQP by up to 30% in both criteria. The benchmark's resources and a solution evaluation script are made openly available.

Martim Brandao, Yukitoshi Minami Shiguematsu, Kenji Hashimoto et al.

In this paper we tackle the problem of visually predicting surface friction for environments with diverse surfaces, and integrating this knowledge into biped robot locomotion planning. The problem is essential for autonomous robot locomotion since diverse surfaces with varying friction abound in the real world, from wood to ceramic tiles, grass or ice, which may cause difficulties or huge energy costs for robot locomotion if not considered. We propose to estimate friction and its uncertainty from visual estimation of material classes using convolutional neural networks, together with probability distribution functions of friction associated with each material. We then robustly integrate the friction predictions into a hierarchical (footstep and full-body) planning method using chance constraints, and optimize the same trajectory costs at both levels of the planning method for consistency. Our solution achieves fully autonomous perception and locomotion on slippery terrain, which considers not only friction and its uncertainty, but also collision, stability and trajectory cost. We show promising friction prediction results in real pictures of outdoor scenarios, and planning experiments on a real robot facing surfaces with different friction.