Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 12

Position Papers of the 2017 Federated Conference on Computer Science and Information Systems

FLOUDS: A Succinct File System Structure

, , ,

DOI: http://dx.doi.org/10.15439/2017F535

Citation: Position Papers of the 2017 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 12, pages 51–57 ()

Full text

Abstract. To spot malicious manipulation, remote attestation and maintenance for devices that are under legal control is very important. One example are measuring instruments, where the manufacturer and the market surveillance want to check if system integrity is preserved. In Europe, legal requirements state that a software identifier needs to be supplied/output by the device, which is often just a checksum over the files that are considered to be legally relevant for the measuring purpose. As measuring instruments and also other legally monitored devices are often small embedded systems, the need for a fast algorithm arises that creates a small file system list containing as much information as possible. In this paper, a new file system structure called FLOUDS is explained that fulfills these requirements. The FLOUDS uses theoretical optimal space to represent the file system structure, while it, nevertheless, enables fast file searches by names and also properties. For example, all files of a specific file type, e.g., pictures, movies, executables, etc., can be listed in O(p lg n) time, where p is the number of files of the specific file type searched for, and, where n represents the total number of file types in the system.

References

  1. D. Arroyuelo, R. Cánovas, G. Navarro, and K. Sadakane. Succinct trees in practice. In Proc. ALENEX, pages 84–97. SIAM, 2010. https://doi.org/10.1137/1.9781611972900.9
  2. J. Arz and J. Fischer. LZ-Compressed String Dictionaries. In Data Compression Conference (DCC), pages 322 – 331, 2014. https://doi.org/10.1109/DCC.2014.36
  3. J. Barbay, F. Claude, and G. Navarro. Compact rich-functional binary relation representations. In Proc. LATIN, volume 6034 of LNCS, pages 170–183. Springer, 2010. https://doi.org/10.1007/978-3-642-12200-2_17
  4. D. Belazzougui and G. Navarro. New lower and upper bounds for representing sequences. In Proc. ESA, volume 7501 of LNCS, pages 181–192. Springer, 2012. https://doi.org/10.1007/978-3-642-33090-2_17
  5. D. Benoit, E. D. Demaine, J. I. Munro, R. Raman, V. Raman, and S. S. Rao. Representing trees of higher degree. Algorithmica, 43(4):275–292, 2005. https://doi.org/10.1007/s00453-004-1146-6
  6. D. K. Blandford, G. E. Blelloch, and I. A. Kash. Compact representations of separable graphs. In Proc. SODA, pages 679–688. ACM/SIAM, 2003. http://doi.acm.org/10.1145/644108.644219
  7. D. K. Blandford, G. E. Blelloch, and I. A. Kash. An experimental analysis of a compact graph representation. In ALENEX/ANALC, pages 49–61. SIAM, 2004. https://doi.org/10.1109/BOD.2006.320815
  8. M. Burrows and D. Wheeler. A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, 1994.
  9. D. Clark. Compact Pat Trees. Phd Thesis presented to the University of Waterloo, Canada. 1996.
  10. P. Davoodi, R. Raman, and S. R. Satti. Succinct representations of binary trees for range minimum queries. In Proc. COCOON, LNCS, pages 396–407. Springer, 2012. https://doi.org/10.1007/978-3-642-32241-9_34
  11. J. Esmet, M. A. Bender , M. Farach-Colton, and B. C. Kuszmaul. The TokuFS streaming file system. In Proceedings of the 4th USENIX Workshop on Hot Topics in Storage (HotStorage), 2012.
  12. A. Farzan and J. Fischer. Compact representation of posets. In Proc. ISAAC, volume 7074 of LNCS, pages 302–311. Springer, 2011. https://doi.org/10.1007/978-3-642-25591-5_32
  13. A. Farzan and J. I. Munro. Succinct representation of arbitrary graphs. In Proc. ESA, volume 5193 of LNCS, pages 393–404. Springer, 2008. https://doi.org/10.1007/978-3-540-87744-8_33
  14. A. Farzan and J. I. Munro. A uniform approach towards succinct representation of trees. In Proc. SWAT, volume 5124 of LNCS, pages 173–184. Springer, 2008. https://doi.org/10.1007/978-3-540-69903-3_17
  15. P. Ferragina and R. Venturini. The compressed permuterm index. In ACM Trans. Algorithms 7, 1, Article 10, 21 pages, 2010. https://doi.org/10.1145/1277741.1277833
  16. J. Fischer and D. Peters. A Practical Succinct Data Structure for Tree-Like Graphs. In WALCOM: Algorithms and Computation, pages 65–76, Springer, 2015. https://doi.org/10.1007/978-3-319-15612-5_7
  17. C. Gavoille and N. Hanusse. On compact encoding of pagenumber k graphs. Discrete Mathematics & Theoretical Computer Science, 10(3):23–34, 2008.
  18. R. F. Geary, N. Rahman, R. Raman, and V. Raman. A simple optimal representation for balanced parentheses. Theor. Comput. Sci., 368(3):231–246, 2006. https://doi.org/10.1007/978-3-540-27801-6_12
  19. S. Gog and J. Fischer Advantages of Shared Data Structures for Sequences of Balanced Parentheses. In Proceedings of the 2010 Data Compression Conference (DCC’10), IEEE Press, pages 406–415, 2010. http://doi.org/10.1109/DCC.2010.43
  20. S. Gog and E. Ohlebusch. Fast and lightweight LCP-array construction algorithms. In Proc. ALENEX, pages 25–34. SIAM, 2011. http://dx.doi.org/10.1137/1.9781611972917.3
  21. A. Golynski, J. I. Munro, and S. S. Rao. Rank/select operations on large alphabets: a tool for text indexing. In Proc. SODA, pages 368–373. ACM/SIAM, 2006. http://dx.doi.org/10.1145/1109557.1109599
  22. R. González, S. Grabowski, V. Mäkinen, and G. Navarro. Practical implementation of rank and select queries. In Poster Proceedings Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA), pages 27–38, Greece, 2005. CTI Press and Ellinika Grammata. http://dx.doi.org/10.1007/978-3-540-89097-3_18
  23. R. Grossi, A. Gupta, and J. S. Vitter High-order entropy-compressed text indexes. In Proceedings of the 14th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA), pages 841–850. 2003.
  24. R. Grossi and G. Ottaviano. Design of practical succinct data structures for large data collections. In Proc. SEA, volume 7933 of LNCS, pages 5–17. Springer, 2013. http://dx.doi.org/10.1007/978-3-642-38527-8_3
  25. Y. Gurevich, L. Stockmeyer, and U. Vishkin. Solving NP-hard problems on graphs that are almost trees and an application to facility location problems. J. ACM, 31(3):459–473, 1984.
  26. G. Heiser. The Role of Virtualization in Embedded Systems. In Proceedings of the 1st Workshop on Isolation and Integration in Embedded Systems, pages 11–16, 2008. https://doi.org/10.1145/1435458.1435461
  27. G. Heiser, V. Uhlig, and J. LeVasseur. Are Virtual-machine Monitors Microkernels Done Right? SIGOPS Oper. Syst. Rev. 40, 2006. https://doi.org/10.1145/1113361.1113363
  28. M. Hohmuth, M. Peter, H. Härtig, J. S. Shapiro. Reducing TCB Size by Using Untrusted Components: Small Kernels Versus Virtual-machine Monitors. In Proceedings of the 11th Workshop on ACM SIGOPS European Workshop, Leuven, Belgium, pages 19–22, 2004. https://doi.org/10.1145/1133572.1133615
  29. G. J. Jacobson. Space-efficient static trees and graphs. In Proc. FOCS, pages 549–554. IEEE Computer Society, 1989.
  30. W. Jannen, J. Yuan, Y. Zhan, A. Akshintala, J. Esmet, Y. Jiao, A. Mittal, P. Pandey, P. Reddy, L. Walsh, M. Bender, M. Farach-Colton, R. Johnson, B. C. Kuszmaul, and D. E. Porter. BetrFS: A Right-Optimized Write-Optimized File System. In 13th USENIX Conference on File and Storage Technologies (FAST 15), pages 301–315, 2015. https://doi.org/10.1145/2798729
  31. S. Joannou and R. Raman. Dynamizing succinct tree representations. In Proc. SEA, volume 7276 of LNCS, pages 224–235. Springer, 2012. https://doi.org/10.1007/978-3-642-30850-5_20
  32. S. Kannan, M. Naor, and S. Rudich. Implicit representation of graphs. SIAM J. Discrete Math., 5(4):596–603, 1992.
  33. M. Lange, S. Liebergeld, A. Lackorzynski, A. Warg, and M. Peter. L4Android: A Generic Operating System Framework for Secure Smartphones. In Proceedings of the 1st ACM Workshop on Security and Privacy in Smartphones and Mobile Devices, Chicago, IL, USA, pages 39–50, 2011. https://doi.org/10.1145/2046614.2046623
  34. S. Lee, and K. Park. Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts. In Lecture Notes in Computer Science 4580, Springer, pages 95–106, 2007. https://doi.org/10.1007/978-3-540-73437-6_12
  35. A. S. Liebergeld, M. Peter, and A. Lackorzynski. Towards Modular Security-Conscious Virtual Machines. In Proceedings of the Twelfth Real-Time Linux Workshop, Nairobi, Kenya, pages 25–27, 2010.
  36. J. I. Munro. Tables. In Proc. FSTTCS, volume 1180 of LNCS, pages 37–42. Springer, 1996.
  37. J. I. Munro, R. Raman, V. Raman, and S. S. Rao. Succinct representations of permutations. In Proc. ICALP, volume 2719 of LNCS, pages 345–356. Springer, 2003. https://doi.org/10.1007/3-540-45061-0_29
  38. J. I. Munro and V. Raman. Succinct representation of balanced parentheses, static trees and planar graphs. In Proc. FOCS, pages 118–126. IEEE Computer Society, 1997.
  39. J. I. Munro and V. Raman. Succinct representation of balanced parentheses and static trees. SIAM J. Comput., 31(3):762–776, 2001. https://doi.org/10.1109/SFCS.1997.646100
  40. R. Pagh. Low redundancy in static dictionaries with constant query time. SIAM J. Comput., 31(2):353–363, 2001. https://doi.org/10.1137/S0097539700369909
  41. M. Pǎtraşcu. Succincter. In Proc. FOCS, pages 305–313. IEEE Computer Society, 2008. https://doi.org/10.1109/FOCS.2008.83
  42. M. Peter, H. Schild, A. Lackorzynski, and A. Warg. Virtual Machines Jailed: Virtualization in Systems with Small Trusted Computing Bases. In Proceedings of the 1st EuroSys Workshop on Virtualization Technology for Dependable Systems, Nuremberg, Germany, 2009. https://doi.org/10.1145/1518684.1518688
  43. D. Peters, M. Peter, J.-P. Seifert, and F. Thiel. A Secure System Architecture for Measuring Instruments in Legal Metrology. In MDPI Computers, 4(2), 61 – 86, 2015. https://doi.org/10.1109/I2MTC.2015.7151517
  44. R. Raman, V. Raman, and S. S. Rao. Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. ACM Transactions on Algorithms, 3(4):Article No. 43, 2007. https://doi.org/10.1145/1290672.1290680
  45. K. Sadakane. Compressed suffix trees with full functionality. Theory Comput. Syst, 41(4):589–607, 2007. https://doi.org/10.1007/s00224-006-1198-x
  46. A. Velosa, J. F. Hines, H. LeHong, E. Perkins, R. M Satish. Predicts 2015: The Internet of Things. In https://www.gartner.com/doc/2952822/predicts--internet-things, 2014.
  47. J. Ziv and A. Lempel Compression of individual sequences via variablerate coding. In Information Theory, IEEE Transactions, 24(5), pages 530–536, 1978.