臺灣博碩士論文加值系統

時脈偏移的測量在時間同步通訊協定、遠距通訊延遲測量等應用至為重要，而時脈偏移也可以作為實體裝置的識別手段。
欲測量網路上另一裝置的時脈偏移，目前的方式是由受測裝置多次傳送時間戳記，量測方收集時間戳記並紀錄包含延遲的偏移量，再使用線性規劃法計算數據分布的下界值，但此法在非典型時間戳記分布的環境下無法獲得精確的結果。本研究針對以下幾種非典型數據分布提出對應的量測方式:(1) 離群值出現在主群體下方 (2) 數據呈現雙峰分布 (3) 數據呈現多段分布 (4) 數據成虛線狀分布。

本研究首先提出基於霍氏轉換的量測法，此法藉由檢索主群體並過濾離群值的方式取得結果，適用於主群體上下方皆出現離群值之情形。針對一千筆典型分布的偏移量作連續量測後，發現霍氏轉換法的估計值震盪幅度為 0.59 ppm、線性規劃法為 0.89 ppm; 若為離群值出現在主群體下方之非典型情況，霍氏轉換法為 1.34 ppm、線性規劃法則為 63.93 ppm。當主群體下方的離群值增加且呈雙峰分布時，本研究引入二項分群法與霍氏轉換法結合以解決此特例。 原始方法僅能將數據辨識為一個寬 2700 us 之群體、新方法則能判斷出二個群體, 每一群體寬 500 us。當數據為多段分布時，本研究將霍氏轉換法擴展為動態區間法來偵測斷點，若斷點發生則視為一分段。針對一個4分段的數據分布，新方法與還原成典型分布後的數據相較誤差僅在 0.22 ppm 之間。

最後針對數據以虛線狀分布之情形，本研究提出了數據重建法作因應。本研究運用線狀分布之特性將離群值修正至理想位置，再以修正過之數據作估算時脈偏移。與未做數據重建的結果相比，原方法辨識幅度為 2.1 ppm，新方法則為 0.9 ppm，結果顯示數據重建法能有效降低運算誤差。此外，數據重建法亦能套用在典型數據分布中。原始方法僅使用 50% 之數據作運算，新數據則為 70%。若以密度觀點分析，原方法僅將數據辨識為寬 1100 us、覆蓋率為 50% 之群體;新方法則為寬 300 us、覆蓋率為 70% 之群體。新方法能將更多數據納入運算時的考量，亦能增加運算結果的精確程度。非典型數據分布皆能以本論文提出之方式解決，因此時脈偏移之裝置驗證機制已然成熟完備。

Accurate clock skew measurements of remote devices over network connections are crucial to device fingerprinting and other related applications. Current approaches use the lower bound of time offsets between the target device and the measurer to estimate clock skew. However, the accuracy of estimation is severely affected when the offsets form non-classical distributions. This study offers new methods to estimate accurately the clock skew of offsets with the following non-classical distributions: 1) offsets contain lower outlier, or offsets that appear below the crowd of offsets, 2) offsets with two populations of crowd of offsets, 3) offsets that are broken by segmentation, and 4) offsets that form parallel dotted lines.

This dissertation first introduces the Hough transform (HT)-based skew method, which searches for the region of offsets majority (ROM) of the whole distribution. This method is effective in filtering out the upper and lower outliers such that the skew values derived from the remaining offsets are stable. During the five consecutive experimental evaluations of 1000 offsets each, skews of the HT-based skew method varied within a range of 0.59 ppm, whereas linear programming algorithm (LPA) resulted in a range of 0.89 ppm. Both ranges increased to 1.34 ppm and 63.93 ppm, respectively, when the lower bounds encountered interference from lower outliers. The HT-based skew method is then extended to bound individually the two crowds of offsets that appear when the population of lower outliers increases. Compared with the original method that can only bound one crowd of offsets with a large ROM of size 2700 us, the extended method offers a more convincing estimation where the two crowd of offsets are bounded by small ROMs with size of 500 us. To estimate the clock skew of offsets that are broken by segmentation, the HT-based skew method is once again extended into a dynamic region of offset majority locating (DROML) method. DROML uses ROM of the HT-based skew method both to measure the skew of one segment and to detect the break between adjacent segments. DROML, when estimating a four-segment case, is able to output a skew of only 0.22 ppm error, compared with the result of the normal case.

For offsets that form parallel dotted lines, this study develops an offsets reconstruction method to return the outliers back into their origin positions, in order to provide ideal offsets for clock skew measurements. By comparing the clock skews of an original sample with the clock skews of the reconstructed sample, an improvement of accuracy from 2.1 ppm to 0.9 ppm is obtained. This improvement proves the robustness of the offsets reconstruction method. Afterwards, the offsets reconstruction method is extended to reconstruct the outliers of offsets with classical distribution.
The evaluation shows that the extended reconstruction method improves the involvement of offsets in the skew estimation of classical offsets from 50% to 70%. In terms of offsets density, the extended reconstruction method compresses the distribution of classical offsets, indicated by a small ROM of 300 us that covers 70% of offsets in the reconstructed sample compared with a large ROM of 1100 us that covers only 50% of offsets in the original sample. These reconstruction results raise the confidence level of the skew estimation on classical offsets as more offsets are involved but in a more dense distribution. As each of the non-classical offsets distributions has been handled accurately, it can be concluded that the clock skew measurement methods offered in this research are robust in estimating the clock skews of devices over network connections.

I. Introduction
II. Clock Skew Measurement and its Limitations
III. Hough Transform-Based Clock Skew Measurement
IV. Improvements on the HT-Based Skew Method
V. Dynamic Region of Offset Majority Locating (DROML) Method for Multisegment Cases
V. Offsets Reconstruction Method
VI. Conclusions

[1] V. Paxson, “On calibrating measurements of packet transit times,” in Proc. ACM SIGMETRICS Conf.,
pp. 11–21, 1998.
[2] S. Moon, P. Skelly, and D. Towsley, “Estimation and removal of clock skew from network delay
measurements,” in Proc. INFOCOM Conf., pp. 227–234, 1999.
[3] T. Kohno, A. Broido, and K. Claffy, “Remote physical device fingerprinting,” IEEE Trans. Dependable
and Secure Computing, vol. 2, no. 2, pp. 93–108, 2005.
[4] J. Bi, Q. Wu, and Z. Li, “On estimating clock skew for one-way measurements,” Comput. Commun.,
vol. 29, pp. 1213–1225, May 2006.
[5] H. Khlifi and J. Grégoire, “Low-complexity offline and online clock skew estimation and removal,”
Comput. Networks, vol. 50, pp. 1872–1884, Aug. 2006.
[6] M. Aoki, E. Oki, and R. Rojas-Cessa, “Measurement scheme for one-way delay variation with detection
and removal of clock skew,” ETRI J., vol. 32, pp. 854–862, Dec. 2010.
[7] S. Murdoch, “Hot or not: revealing hidden services by their clock skew,” in Proc. 13th ACM Conf.
Comput. and Commun. Security, pp. 27–36, 2006.
[8] S. Zander and S. Murdoch, “An improved clock-skew measurement technique for revealing hidden
services,” in Proc. 17th Conf. Security Symp., pp. 211–225, 2008.
[9] D.-J. Huang, W.-C. Teng, C.-Y. Wang, H.-Y. Huang, and J. M. Hellerstein, “Clock skew based node
identification in wireless sensor networks,” in IEEE Global Telecommun. Conf. (GLOBECOM), 2008.
[10] D.-J. Huang and W.-C. Teng, “A defense against clock skew replication attacks in wireless sensor
networks,” J. Network and Comput. Applicat., vol. 39, pp. 26–37, Mar. 2014.
[11] D.-J. Huang, W.-C. Teng, and K.-T. Yang, “Secured flooding time synchronization protocol with moderator,”
Int. J. Commun. Syst., vol. 26, no. 9, pp. 1092–1115, 2013.
[12] X. Mei, D. Liu, K. Sun, and D. Xu, “On feasibility of fingerprinting wireless sensor nodes using
physical properties,” in 27th IEEE Int. Symp. Parallel and Distributed Process. (IPDPS), pp. 1112–
1121, May 2013.
[13] M. B. Uddin and C. Castelluccia, “Toward clock skew based wireless sensor node services,” in 5th
Annu. ICST Wireless Internet Conf. (WICON), pp. 1–9, 2010.
[14] C. Arackaparambil and S. Bratus, “On the reliability of wireless fingerprinting using clock skews,” in
Proc. 3rd ACM Conf. Wireless Network Security, pp. 169–174, 2010.
[15] S. Jana and S. Kasera, “On fast and fccurate detection of unauthorized wireless access points using
clock skews,” IEEE Trans. Mobile Comput., vol. 9, pp. 449–462, Mar. 2010.
[16] D.-J. Huang, K.-T. Yang, C.-C. Ni, W.-C. Teng, T.-R. Hsiang, and Y.-J. Lee, “Clock skew based client
device identification in cloud environments,” in 26th IEEE Int. Conf. Advanced Inform. Networking
and Applicat. (AINA), pp. 526–533, Mar. 2012.
[17] S. Sharma, H. Saran, and S. Bansal, “An Empirical study of clock skew behavior in modern mobile
and hand-held devices,” in 3rd Int. Conf. Commun. Syst. and Networks (COMSNETS), pp. 1–4, Jan.
2011.
[18] S. Sharma, A. Hussain, and H. Saran, “Experience with heterogenous clock-skew based device fingerprinting,”
in Proc. LASER Workshop, pp. 9–18, 2012.
[19] M. Cristea and B. Groza, “Fingerprinting smartphones remotely via ICMP timestamps,” IEEE Commun.
Lett., vol. 17, pp. 1081–1083, June 2013.
[20] L. Polcák, J. Jirásek, and P. Matousek, “Comment on ”Remote Physical Device Fingerprinting”,” IEEE
Trans. Dependable and Secure Computing, vol. 11, pp. 494–496, 2014.
[21] R. O. Duda and P. E. Hart, “Use of the Hough transformation to detect lines and curves in pictures,”
Commun. ACM, vol. 15, pp. 11–15, Jan. 1972.
[22] P. Hart, “How the Hough transform was invented,” IEEE Signal Process. Mag., vol. 26, no. 6, pp. 18–
22, 2009.
[23] Z.-H. Chen, A. W. Y. Su, and M.-T. Sun, “Resource-efficient FPGA architecture and implementation
of Hough Transform,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 20, pp. 1419–1428, Aug.
2012.
[24] B. W. Silverman, “Using kernel density estimates to investigate multimodality,” Journal of the Royal
Statistical Society: Series B, vol. 43, pp. 97–99, 1989.
[25] J. A. Hartigan and P. M. Hartigan, “The dip test of unimodality,” The Annals of Statistics, vol. 13,
pp. 70–84, 1985.
[26] G. McLachlan and D. Peel, Finite Mixture Models. Hoboken, NJ: Wiley, 2000.
[27] J. Freeman and R. Dale, “Assessing bimodality to detect the presence of a dual cognitive process,”
Behaviour Research Method, vol. 45, pp. 56–62, July 2013.
[28] F. Melcher, “Hartigan’s Dip Statistic.” http://www.nicprice.net/diptest/. Accesed: 2016-5-
15.
[29] N. Otsu, “A threshold selection method from gray-level histograms,” IEEE Trans. Sys., Man., Cyber.,
vol. 9, no. 1, pp. 62–66, 1979.
[30] A. Greensted, “Otsu Thresholding.” http://www.labbookpages.co.uk/software/imgProc/
otsuThreshold.html. Accesed: 2016-5-15.
[31] T. E. Abrudan, A. Haghparast, and V. Koivunen, “Time synchronization and ranging in OFDM systems
using time-reversal,” IEEE Trans. Instrum. Meas., vol. 62, pp. 3276–3290, Dec. 2013.
[32] T. Cooklev, J. C. Eidson, and A. Pakdaman, “An implementation of IEEE 1588 over IEEE 802.11b
for synchronization of wireless local area network nodes,” IEEE Trans. Instrum. Meas., vol. 56, no. 5,
pp. 1632–1639, 2007.
[33] C. D. Dominicis and P. Pivato, “Timestamping of IEEE 802.15.4a CSS signals for wireless ranging
and time synchronization,” IEEE Trans. Instrum. Meas., vol. 62, no. 8, pp. 2286–2296, 2013.
[34] A. Vakili and J.-c. Grégoire, “Accurate one-way delay estimation: limitations and improvements,”
IEEE Trans. Instrum. Meas., vol. 61, no. 9, pp. 2428–2435, 2012.
[35] K. Zeng, K. Govindan, and P. Mohapatra, “Non-cryptographic authentication and identification in
wireless networks,” IEEE Wireless Commun., vol. 17, no. 5, pp. 56–62, 2010.
[36] L. Zhang, Z. Liu, and C. H. Xia, “Clock synchronization algorithms for network measurements,” in
Proc. INFOCOM Conf., pp. 160–169, 2002.
[37] S. Johannessen, “Time synchronization in a local area network,” IEEE Control Systems, vol. 24,
pp. 61–69, Apr. 2004.
[38] Y.-C. Wu, Q. Chaudhari, and E. Serpedin, “Clock synchronization of wireless sensor networks,” IEEE
Signal Proc. Magazine, vol. 28, pp. 124–138, Jan. 2011.
[39] L. De Vito, S. Rapuano, and L. Tomaciello, “One-way delay measurement: state of the art,” IEEE
Trans. Instrum. Meas., vol. 57, pp. 2742–2750, Dec. 2008.
[40] A. Vakili and J.-C. Gregoire, “Accurate one-way delay estimation: limitations and improvements,”
IEEE Trans. Instrum. Meas., vol. 61, pp. 2428–2435, Sept. 2012.
[41] C. D. Dominicis, P. Ferrari, A. Flammini, and E. Sisinni, “Wireless sensors exploiting IEEE802.15.4a
for precise timestamping,” in Proc. ISPCS 2010 Conf., pp. 48–54, 2010.
[42] W. Dong and X. Liu, “Robust and secure time-synchronization against sybil attacks for sensor networks,”
IEEE Trans. Industrial Informatics, vol. 11, pp. 1482–1491, Dec. 2015.
[43] A. Boukerche and D. Turgut, “Secure time synchronization protocols for wireless sensor networks,”
IEEE Wireless Commun., vol. 14, pp. 64–69, Oct. 2007.
P. Ferrari, G. Giorgi, C. Narduzzi, S. Rinaldi, and M. Rizzi, “Timestamp validation strategy for wireless
sensor networks based on IEEE 802.15.4 CSS,” IEEE Trans. Instrum. Meas., vol. 63, no. 11, pp. 2512–
2521, 2014.
[45] T. Cooklev, J. C. Eidson, and A. Pakdaman, “An implementation of IEEE 1588 over IEEE 802.11b
for synchronization of wireless local area network nodes,” IEEE Trans. Instrum. Meas., vol. 56, no. 5,
pp. 1632–1639, 2007.
[46] K. Oka Saputra, W.-C. Teng, and P.-Y. Chou, “A study of regular transmission delay in bluetooth
communications,” in Proc. of the 3rd International Conf. on Intelligent Technologies and Engineering
Systems (ICITES), pp. 301–307, 2014.
[47] K. Oka Saputra, W.-C. Teng, and T.-H. Chen, “Hough transform-based clock skew measurement over
network,” IEEE Trans. Instrum. Meas., vol. 64, Dec. 2015.
[48] K. Oka Saputra, W.-C. Teng, and Y.-H. Chu, “A clock ckew replication attack detection approach utilizing the resolution of system time,” in Proc. 2015 IEEE/WIC/ACM International Conf. on Web
Intelligence and Intelligent Agent Technology, pp. 211–214, 2015.
[49] K. Oka Saputra, W.-C. Teng, and T. Nara, “Hough transform-based clock skew measurement by dinamically locating the region of offsets majority,” IEICE Trans. Inf. and Syst., 2016. To appear in print.