TOP > Research > Comprehensive List of Researchers "Information Knowledge" > Department of Information Engineering > Software Science and Technology Group > SEKI, Hiroyuki

Comprehensive List of Researchers "Information Knowledge"

Department of Information Engineering

Name
SEKI, Hiroyuki
Group
Software Science and Technology Group
Title
Professor
Degree
Dr. of Engineering
Research Field
Formal Language Theory / Software Design and Verification
SEKI, Hiroyuki

Current Research

Language-based Security and Privacy/Mildly Context-Sensitive Grammars

1. Design and Verification of Safe, Secure and Reliable Software

(1) Infinite-State Model Checking
Model checkers such as SMV and SPIN have been widely used for automatically verifying the correctness of software systems. These model checking algorithms have been extended so that an infinite-state system such as a pushdown system (PDS) can also be automatically verified. We are applying infinite-state model checking methods to the security issues of software systems. We will give an example of our research in this direction.
A confidential data might be leaked, modified or even broken by a malicious code downloaded via the internet. To avoid such an attack, runtime programming language environments such as JDK and CLR provide access control mechanisms, e.g., sandbox and stack inspection. However, it is not an easy task to determine when, where and how access rights should be checked during the execution of given software. Based on a PDS model checking algorithm, we developed a method of automatically inserting check points for runtime access control into a given program to satisfy a given security policy.

(2) Tree Language Theory and Its Application to XML Document Transformation

XML is a de facto standard for data storage and exchange. A tree is a simple data structure that can naturally represent the hierarchical structure in an XML document. A tree automaton and a tree transducer are a natural extension of a finite-state automaton and a string transducer, respectively. A schema of an XML database can be modeled by a tree automaton and a query to an XML database can be modeled by a tree transducer. By using these models, we are conducting the following topics:
- XML data compression using tree grammars, and direct manipulation of compressed XML data
- Decidability and computational complexity of k-secrecy of XML database/schema against inference attacks
- Decidability and computational complexity of information preservation of XML data transformation

(3) Quantitative Measures for Security and Privacy

Recently, quantitative notions for security and privacy of software are paid much attention. Those notions include k-anonymity, quantitative information flow and differential privacy. These quantitative notions are necessary to measure how much the confidential data and private information are leaked by observing the data that are legally disclosed. We investigate the following related topics:
- Measuring quantitative information flow by static analysis and model counting
- Sanitization method to obtain a good trade-off between privacy and utility
- k-anonymization of structured data

(4) Mildly Context-Sensitive Grammar and Its Application
We proposed multiple context-free grammar (MCFG) as a natural extension of context-free grammar (CFG). The generative power of MCFG is strictly stronger than CFG and strictly weaker than context-sensitive grammar. MCFG inherits from CFG good properties such as closure properties on language operations and polynomial-time recognizability. Besides purely theoretical research, we apply MCFG to fundamental problems in bioinformatics. Predicting the structures of biological sequences such as DNA and RNA from primary structures is important for understanding the function of those sequences. Parsing algorithms of formal grammars can be used to predict the structure of those sequences. However, RNA contains the substructures called pseudoknots, which cannot be represented by CFG. MCFG, on the other hand, can concisely represent pseudoknots. Using a parsing algorithm of MCFG, we implemented a tool for predicting the structure of RNA and showed its effectiveness based on the experiments conducted for real RNA datasets.

Career

  • (Professional Experience)
    • April 2013 - Present: Professor
    •   Graduate School of Information Science, Nagoya University
    • October 1996 – March 2013: Professor
    • April 1994 - September 1996: Associate Professor
    •   Graduate School of Information Science, Nara Institute of Science and Technology
    • March 1996 - September 1996: Visiting Researcher
    •   Computer Systems Research Institute, University of Toronto
    • December 1992 - March 1994: Associate Professor (Jokyouju)
    • October 1990 - November 1992: Assistant Professor (Koushi)
    • April 1987 - September 1990: Assistant Professor (Joshu)
    •   Department of Information and Computer Sciences, Osaka University
    •   
  • (Education)
    • March 1987: Dr. Eng. in Information and Computer Sciences, Osaka University
    • March 1982: B. Eng. in Information and Computer Sciences, Osaka University

Academic Societies

  • IEICE
  • JSSST

Publications

  1. Yuki Kato, Tatsuya Akutsu and Hiroyuki Seki, A Grammatical Approach to RNA-RNA Interaction Prediction, Pattern Recognition, 42, 531-538, April 2009.
  2. Yasunori Ishihara, Toshiyuki Morita, Hiroyuki Seki and Minoru Ito, An Equational Logic Based Approach to the Security Problem against Inference Attacks on Object-Oriented Databases, Journal of Computer and System Sciences, 73, 788-817, 2007.
  3. Jing Wang, Yoshiaki Takata and Hiroyuki Seki, HBAC: A Model for History-based Access Control and Its Model Checking, 11th European Symposium On Research In Computer Security (ESORICS 2006), Hamburg, Germany, Sept. 2006, Lecture Notes in Computer Science 4189, pp.263-278.
  4. Yasunori Ishihara, Shin Ishii, Hiroyuki Seki and Minoru Ito, Temporal Reasoning about Two Concurrent Sequence of Events, SIAM Journal on Computing, 34(2), 498-513, 2005.
  5. Hiroyuki Seki, Toshinori Takai, Youhei Fujinaka and Yuichi Kaji, Layered Transducing Term Rewriting System and Its Recognizability Preserving Property, 13th International Conference on Rewriting Techniques and Applications (RTA 2002), Copenhagen, Denmark, July 2002, Lecture Notes in Computer Science 2378, pp.98-113.
  6. Naoya Nitta, Yoshiaki Takata and Hiroyuki Seki, An Efficient Security Verification Method for Programs with Stack Inspection, 8th ACM Conference on Computer and Communications Security (CCS 2001), pp.68-77, Philadelphia, Pennsylvania, Nov. 2001.
  7. Yasunori Ishihara, Shogo Shimizu, Hiroyuki Seki and Minoru Ito, Refinements of Complexity Results on Type Consistency for Object-Oriented Databases, Journal of Computer and System Sciences, 62(4), 537-564, 2001.        
  8. Toshinori Takai, Yuichi Kaji and Hiroyuki Seki, Right-Linear Finite Path Overlapping Term Rewriting Systems Effectively Preserve Recognizability, 11th International Conference on Rewriting Techniques and Applications (RTA 2000), Norwich, U.K. July 2000. Lecture Notes in Computer Science 1833, 246-260.
  9. Yuichi Kaji, Ryuichi Nakanishi, Hiroyuki Seki and Tadao Kasami, The Computational Complexity of the Universal Recognition Problem for Parallel Multiple Context-Free Grammars, Computational Intelligence, 10(4), 431-443, Nov. 1994.
  10. Hiroyuki Seki, Ryuichi Nakanishi, Yuchi Kaji, Sachiko Ando and Tadao Kasami, Parallel Multiple Context-Free Grammars, Finite-State Translation Systems and Polynomial-Time Recognizable Subclasses of Lexical-Functional Grammars, 31st Annual Meeting of the Association for Computational Linguistics (ACL 1993), pp.130-139, Columbus, Ohio, June 1993.
  11. Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii and Tadao Kasami, On Multiple Context-Free Grammars, Theoretical Computer Science, 88(2), 191-229, Oct. 1991.
  12. Katsuro Inoue, Hiroyuki Seki and Hikaru Yagi, Analysis of Functional Programs to Detect Run-Time Garbage Cells, ACM Transactions on Programming Languages and Systems, 10(4), 555-578, Oct. 1988.