以有限狀態自動機達成XML簽章驗證的線性化

Abstract

XML簽章的主要瓶頸在於Canonical XML, Canonical XML是W3C定義正規化XML文件的方法,此正規化流程稱為Canonicalization (C14n),降低C14n的複雜度就能大幅提升XML簽章的效能,此研究提供一個轉換模型來降低C14n的複雜度,在執行XML正規化的過程中透過以有限狀態自動機為基礎的轉換模型將每一個XML節點轉換成非遞迴的序列,在簽章驗證的過程中透過一個有限狀態轉換器就能在線性時間內將此序列還原回Canonical XML,本研究提出得方法可以在XML簽章驗證時將正規化XML的複雜度降至O(n),此方法同時具有streaming的特性,可以大幅降低記憶體使用率及提升運算速度,適合使用於如防火牆及行動裝置這類低資源及低運算能力的裝置上。

XML Signature main bottleneck is Canonical XML. Canonical XML is a formalization method for XML document defined in W3C Canonical XML [9]. This formalize process called Canonicalization (C14n). Reducing the complexity of C14n can also significantly improve the performance of XML Signature. This research provides a transformation model to reduce the complexity of C14n. In the processing of C14n, the results of node operations are converted to non-recursive binary sequence by the transformation model based on Finite Automata. For signature verification, the binary sequence can be restored into Canonical XML by Finite Automata in linear time. The proposed scheme can reduce the complexity of Canonical XML to O(n) and streaming characteristics. The characteristics of streaming can also substantially reduce memory usage and improve computing speed. This scheme is suitable for applications such as firewall or mobile devices with limited -resource or low computing capability.