Maciej Rostański
email: mrostanski@wsb.edu.pl

Taras Mushynskyy

Maciej Rosta

Security issues of IPv6 network autoconguration

Keywords: Security Issues of IPv6 Network Autoconfiguration IPv6, Computer Networks, Network Security, SLAAC, DHCPv6

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

1 Introduction. On the verge of the Internet of Things Networks are growing endlessly and more and more data is being processed every day. For example, only by utilizing the amount of sensors gathering data, the Internet is becoming huge infrastructure for aggregation and delivery of constant data for the end-systems. The concept of this, called The Internet of Things, is a bit futuristic expression created by K. Ashton (see [START_REF] Ashton | That 'Internet of Things' Thing[END_REF]). The idea is that not only typical computers, smartphones or tablets will use network for communication -but any device will. This is very relevant to the IPv6 adoption -as the IPv6 major feature is a huge addressing space and simplied network conguration, supporting massive scalability of networks, at the same time enabling end-toend communication with devices connected to internetwork. Once enabled, this concept creates endless possibilities -such as the Talking Tree Project 1 , a very interesting idea of equipping a tree with sensors, cameras, etc. and utilizing complex software allowing a tree to literally tweet about the weather, noises, wind changes.

Migration to IPv6 protocol with its vast address space is a step forward into those and many other possibilities for innovative services. This is a major IPv6 adoption driver for innovative enterprises, and many of small and medium organizations are considering migration. Although the dynamics of IPv6 protocol deployment is not as high as expected, experts assume it is going to grow for a couple of next years [START_REF] Curtis | Internet of Things: miliardy urz¡dze«, czujników i liczników podª¡czonych do sieci[END_REF]. There is an overall impression, that only legacy applications hold back the migration for many organizations, especially when they learn about many advantages of IPv6, such as simple autoconguration mechanisms.

This article shows a dierent perspective on this matter.

1.1 IPv6 is not about bigger address space only IPv6 protocol, being a successor to the most popular network layer protocol, is thoroughly described in RFCs and in numerous literature, such as [START_REF] Van Beijnum | Running IPv6[END_REF], [START_REF] Odom | CCNP Route 642-902 Ocial Certication Guide 4[END_REF] or [START_REF] Deering | Internet Protocol, Version 6 (IPv6) Specication, RFC 2460[END_REF]. There are many advantages of IPv6 over IPv4 protocol, which, among many benets, include: multi-addressing, which basically means, the node may have many IPv6 addresses, related to its function and connectivity, as well as address scope simplied network conguration, relying on automatic host addressing and routers sending the prexes in router advertisements, directed data ows, utilizing multicast rather than broadcast transmission -in addition, IPv6 header includes Flow Label eld for identifying packets within the same ow, simplied packet header, meaning more ecient packet processing -for example, there is no IP-level checksum, true end-to-end connectivity, restored by eliminating the need for Network Address Translation, authentication and privacy capabilities, built into protocol itself.

For many years, there is a discussion still active, whether it is a good time to migrate to IPv6. As years went by, it was becoming clearer that IPv4 is not going to vanish entirely in a fast manner; some even predict that a dual IP protocol coexistence is going to last a very long time. The organizations are reluctant in IPv6 adoption. Arbor Networks study cited in [START_REF] Burkhalter | Study: IPv6 adoption remaining slow, Perle Industry News[END_REF] indicates that possible obstacles to adoption include lack of economic incentives, lack of existing IPv6 content and technical and design hurdles.

On the other hand, the IPv4 address space is shrinking rapidly; on September 2012, RIPE NCC ran out of IPv4 addresses 2 . Technical problems diminish: most of modern operating systems are fully IPv6 capable, the network equipment is IPv6 ready, and IPv6 knowledge is becoming more and more common.

According to the Author, the best thing about IPv6 protocol is the most surprising one: IPv6 is in fact simpler in conguration and more ecient in deployment than IPv4. Many administrators would disagree and point out the 2 Further information: http://arstechnica.com/information-technology/2012/ 09/europe-officially-runs-out-of-ipv4-addresses/ complexity of IPv6 address compared to IPv4, however considering other features, like stateful and stateless autoconguration of network nodes, mobility support, mandatory security protocols support, the above statement is quite defendable.

About this paper

Myths and benets of IPv6 deployment are very well described by Van Beijnum in [START_REF] Van Beijnum | Running IPv6[END_REF]. The ease of conguration creates risks -some administrators would just plug the network equipment in and, while it works, won't bother with security checks. That's why this article is important -it focuses on the presentation of autoconguration mechanisms risks in IPv6. The protocols and messages used during autocongurations are described in section 2; section no. 3 presents several security issues related to the autoconguration protocols. Section 4 presents a real-life case scenario and the results of eld testing.

About automatic address conguration in IPv6

The useful advantage of IPv6 protocol, most relevant to the subject of this paper, is allowing network nodes to address themselves on their own or with Neighbor Discovery Protocol is called SLAAC (Stateless address autoconguration).

Although there are tasks, for implementation of that greater control is needed besides addressing in LAN networks. At that case it is necessary to use the static addressing or DHCP server for IPv6 protocol (DHCPv6).

As the rst step, every host congures link-local address on every IPv6enabled interface. In early IPv6 documentation, the address should almost everytime be derived from layer 2 address (e.g. MAC address) -now, it is not the case (see [START_REF] Narten | Privacy Extensions for Stateless Address Autoconguration in IPV6[END_REF]), for example Microsoft Windows 7 or 8 congures its host address portion randomly. In any case, the IPv6 host is supposed to perform a DAD (Duplicate Address Detection) operation. Once link-local address is congured, the autoconguration operation commences. The entire process is described in [START_REF] Thomson | IPv6 Stateless Address Autoconguration (RFC 4862), Draft Standard, IETF 2007[END_REF]. Just to provide short overview, the process relies on: a) IPv6 router sending out RAs (Router Advertisements) periodically and ondemand (as a response to RS message -Router Solicitation), b) Hosts sending RS messages and obtaining RA information, such as an address prex and a lease lifetime. 3 Automatic conguration security issues Unfortunately, IPv6 congurations may impose a vulnerability threats in many situations, when improperly used. An example of such problems involve using fragmentation for attacks on IPv6 network, such as overlapping fragments, Paxson/Shankar model [START_REF] Novak | Target-Based Fragmentation Reassembly[END_REF] or Rose attack [START_REF] Hollis | Rose Attack Explained[END_REF], as well as 6to4 tunneling, quoting [START_REF] Van Beijnum | Running IPv6[END_REF]: allowing people to create packets with spoofed IPv6 addresses and encapsulate them in legitimate IPv4 packets, thereby passing anti-spoong lters that may be in eect. Other examples include using tunneling for attacks, DNS advertising or neighbor discovery. As shown before, the stateless conguration allows any IPv6 device to communicate with other IPv6 devices in the same LAN, by advertising its presence, so it can be located by Neighbor Discovery Protocol.

NDP protocol however, cannot be left without supervision; it may allow an attacker to gather network devices data, for example. Further data on this subject is thoroughly described in [START_REF] Narten | Neighbor Discovery for IP version 6 (IPv6) (RFC 4861)[END_REF].

State-of-the-art

The autoconguration mechanisms of an IPv6 protocol are subject to huge research indicating its vulnerabilities, as [START_REF] Chown | IPv6 Router Advertisement Problem Statement[END_REF], [START_REF] Narten | Privacy Extensions for Stateless Address Autoconguration in IPV6[END_REF], [START_REF] Chown | Dynamic Host Conguration Protocol(DHCP): IPv4 and IPv6 Dual-Stack Issues[END_REF] or [START_REF] Durand | Operational Considerations and Issues with IPv6 DNS[END_REF]. There is also well known literature pointing to techniques of securing network behavior, especially: Secure Neighbor Discovery (SEND) [START_REF] Arkko | SEcure Neighbor Discovery (SEND)[END_REF]; IPv6 Router Guard [START_REF] Levy-Abegnoli | IPv6 Router Advertisement Guard[END_REF]; Autocong ltering on Ethernet switches [START_REF] Ward | IPv6 Autocong Filtering on Ethernet Switches, Internet Draft[END_REF]; Implications for Network Scanning [START_REF] Chown | Implications for Network Scanning[END_REF].

Such techniques and mechanisms have been recognized as more or less effective, but are also dicult to congure. With autoconguration in mind, the common practice (for example when setting up a conference network) is to congure the edge router for IPv6 and let the modern operating systems autocongure themselves. The most dangerous fact is, modern operating systems attempt IPv6 autoconguration by default and use IPv6 stack with higher priority than IPv4 [START_REF] Chown | Default Address Selection for Internet Protocol Version 6 (IPv6)[END_REF]. This is extremely probable for example if BYOD (Bring Your Own Device) strategy is deployed without sucient conguration and/or monitoring.

The point of this article is to present vulnerability of such scenario and show yet another security aw -the DHCP 'apping' on an autocongured network.

The malicious behavior scenarios possibilities are discussed in IPv6 related documentation, such as [START_REF] Nikander | IPv6 Neighbor Discovery (ND) Trust Models and Threats, RFC 3756[END_REF] or [START_REF] Arkko | SEcure Neighbor Discovery (SEND)[END_REF]. Mitigating such risks is by all means possible and doesn't mean that IPv6 features are awed; the administrator just has got to have knowledge of such threat and be aware of the conditions imposing a vulnerability. Several techniques for securing IPv6 local trac are considered canonical, such as SEND (SEcure Neighbor Discovery, see [START_REF] Arkko | SEcure Neighbor Discovery (SEND)[END_REF]), other methods are possible but deployed rarely, e.g. IPv6 Router Advertisement Guard [START_REF] Levy-Abegnoli | IPv6 Router Advertisement Guard[END_REF]. The problem is, those solutions are, quoting Levy-Abegnoli, 'non-trivial to deploy' ( [START_REF] Levy-Abegnoli | IPv6 Router Advertisement Guard[END_REF]). In case of non-prepared administrators or low budget for security testing, those techniques won't even be considered. This is sadly a typical experience in small and medium enterprises.

In this section, several autoconguration security issues for default-congured network devices and hosts are described. An administrator should be able to recognize such conditions in his own network and prepare for those situations accordingly. The aim of this work was to create an IPv6 network using DHCP addressing mode and revealing the features of the network equipment's work.

Typical autocoguration scenarios and associated threats

Research topology

For the project we used the following equipment:

Routers: Cisco 1841 with IOS operating system, Switches: Cisco 2950T with IOS operating system, PCs with Microsoft Windows7 Enterprise SP1 operating system, PCs with Microsoft Windows Server 2008 R2 Enterprise SP1 operating system. As a result of conguration, all computers obtained dynamic addresses from DHCP server. DHCP server and routers were assigned static IP addresses. Moreover, the server gave out addresses for both networks LAN1 and LAN2.

Rogue SLAAC router scenario

After verication, it was decided to connect router3 to switch1. Router3 was congured with these commands:

ipv6 unicast-routing ipv6 address 2001:db8:0:1::1/64 (on the interface FastEthernet0/0) ipv6 enable

That is, router3 had IPv6 mode enabled and assigned an IPv6 address to the FastEthernet interface. Accordingly, the automatic address assignment SLAAC was activated, which was enabled by default.

Connecting the router3 to switch1 had signicant eects on the computers in the network LAN1. First, the computer was running using the address obtained from the DHCP server. Then, after a while, the computer received the SLAAC address from Router3. After a few minutes the computer again received address from a DHCP server, but dierent from the rst one. The address lease time at DHCP server was 8 days by default. On the average, changing of IP address occurred in 6-9 minutes. Fig. 4 shows the result of observation, which was carried out using Wireshark snier application. A similar experiment was done in the network LAN3 (Router3 was connected to Switch2). The results of computers behavior were the same as in the network LAN1. Routing protocol RIP was used on routers 1 and 2. If RIP protocol was enabled on Router3, then during IP address change, the computer was still able on aected hosts -this is another vulnerability as described in [START_REF] Chown | IPv6 Router Advertisement Problem Statement[END_REF].

Conclusion

In this article, given security risk scenarios are described as potentially dangerous; eld testing conrming the most interesting scenario was presented as case study. As a result of this work it was shown that two autoconguration methods (one of which is the stateful mode, and the other is a SLAAC mode) would work in IPv6 network with the same priority and hinder the work of each other. This in turn can lead to serious disturbances in the functioning of DHCP serversthe basic service of corporate networks.

This article shows one of many vulnerabilities of an autocongured IPv6 network. Important fact is, given latest BYOD strategies, such autoconguration may occur without administrator's knowledge -modern operating systems support IPv6 by default. This is not indication of a aw -just a reminder, that in IPv6 networks, careful administration of autoconguration must (!) be applied, for example using SEND [START_REF] Arkko | SEcure Neighbor Discovery (SEND)[END_REF].

Fig. 1 Fig. 1 .

 11 Fig.1provides the lifecycle of an autocongured IPv6 address.In simple terms, stateful conguration utilizes an updated version of DHCP for IPv4. The DHCP protocol for IPv6 (DHCPv6) is slightly dierent because it relies on the client sending RS messages, thus detecting the presence of the routers on the link. The steps that follow include[START_REF] Droms | Dynamic Host Conguration Protocol for IPv6 (DHCPv6)[END_REF]: a) If a router is found (RA is received), the RA message is examined for ags indicating whether DHCP can or should be used,

Fig. 2 .

 2 Fig.2. The state-diagram of DHCPv6 operation. Source:[START_REF] Odom | CCNP Route 642-902 Ocial Certication Guide 4[END_REF]

Following

  scenarios are possible if the attacker has access to local network and the IPv6 devices are congured with default security measures. The network doesn't have to be congured for IPv6, all modern devices support IPv6 and the IPv6 stack is turned on by default. Stateless autoconguration with rogue station: This security risk scenario assumes that following conditions are fullled: a) The original network node is autocongured using SLAAC mode with address A1, b) The malicious node is trying to set its address to A1 repeatedly ignoring DAD (Duplicate Address Discovery) messages.The outcome should be IPv6 stack disabled on the second node. However, because of the malicious nature, should the second node continue to send packets, the original node's operating system operation may vary, depending on its manufacturer and version. This is a situation that should be tested for systems used in organization's network. Stateless autoconguration with rogue router: This security risk scenario assumes that following conditions are fullled: a) The network nodes are using SLAAC autoconguration. For this purpose, an original router node is congured to send RAs containing network prex, b) Every node is congured with network prex and default gateway through RA messages, c) The malicious router is being introduced to the network, sending RAs on his own. In the outcome, an administrator would want the nodes to ignore other RAs and this is achievable through specic conguration and network security devices introduction; but the question is: how would default congured equipment behave? This is interesting research subject for various operating systems and versions. Stateful autoconguration with rogue DHCP server: Scenario conditions include: a) Conguring network nodes and DHCPv6 server for a stateful conguration of any device, b) Introducing a malicious DHCPv6 server, competing with an original one. Desired network behavior would be ignoring new DHCP server, until lease expiration time. The device should then ask legitimate server for another lease, choosing another DHCP only in the situation of denial or absence of legitimate DHCP server. Stateful autoconguration with rogue router: Scenario conditions include: a) Conguring network nodes and DHCPv6 server for a stateful conguration of any device, b) Introducing a malicious IPv6 router, sending RAs on his own. Desired network behavior would be ignoring malicious router, until lease expiration time. The device should then ask legitimate server for another lease, choosing RA information only in the situation of denial or absence of legitimate DHCP server. 4 Field study. Rogue SLAAC server vs. legitimate DHCP server example For the study of security issues, the last and most interesting scenario was chosen for eld testing. The scenario consisted of: a) Conguring a typical internetwork with DHCP server, b) Introducing an IPv6 rogue router advertising RAs for stateless autoconguration.

Fig. 3 .

 3 Fig. 3. Test topology. Source: own work

Fig. 4

 4 Fig. 4 shows that the command ping 2001:777:0:3::6 was executed on computer with IP address 2001:777:0:1::d. After changing of addressing in SLAAC mode and returning back to the DHCP provisioned address, IP address of the computer became 2001:777:0:1::c. This change in the DHCP address happened every time, going through all the addresses from scope, thus depleting the available pool. This problem occured on all computers in the network with both Microsoft Windows Server 2008 and Microsoft Windows 7.

Fig. 4 .

 4 Fig. 4. Trac during experiment -the 'apping' between stateless and stateful address. Source: own work

Talking Tree Project Website: http://www.talking-tree.com/

Acknowledgement

Presented work is a part of ongoing research IPv6 role in High Availability and Redundant Networks of Small and Medium Organisations, being conducted in Academy of Business in Dabrowa Gornicza.


Dariusz Frejlichowski
email: dfrejlichowski@wi.zut.edu.pl

Katarzyna Gościewska
email: katarzyna.gosciewska@smartmonitor.pl

Pawe L Forczmański
email: pforczmanski@wi.zut.edu.pl

Adam Nowosielski
email: anowosielski@wi.zut.edu.pl

Rados Law Hofman

The Removal of False Detections from Foreground Regions Extracted using Adaptive Background Modelling for a Visual Surveillance System

Keywords: 'SmartMonitor', visual surveillance system, video content analysis

For recent surveillance systems, the false detection removal process is an important step which succeeds the extraction of foreground regions and precedes the classification of object silhouettes. This paper describes the false object removal process when applied to the 'Smart-Monitor' system -i.e. an innovative monitoring system based on video content analysis that is currently being developed to ensure the safety of people and assets within small areas. This paper firstly briefly describes the basic characteristics and advantages of the system. A description of the methods used for background modelling and foreground extraction is also given. The paper then goes on to explain the artefacts removal process using various background models. Finally the paper presents some experimental results alongside a concise explanation of them.

Introduction

The 'SmartMonitor' system is being developed to combine the advantages of small closed-circuit television systems (CCTV) and visual content analysis algorithms (VCA). It aims to increase the safety of individual clients and their assets -i.e. houses, apartments, shops, enterprises, etc. -and help to ensure security in their surroundings. Through customisation of system parameters, all users will be able to set individual safety rules and adjust the system sensitivity level to suit their actual needs. Such customizability is one of the most important advantages. The system will be an affordable solution and will utilize only commonly available hardware, i.e. a personal computer and digital camera(s). Human participation will be reduced to the minimum and only the calibration process will require user interaction. 'SmartMonitor', as an innovative surveillance system, will utilize specific algorithms to perform video analysis and to react to particular events in pre-specified ways. These algorithms will be integrated into six main system modules responsible for background modelling, object tracking, artefacts removal, object classification, event detection and system response.

The system will operate under four independent scenarios, which concern home/surroundings protection against unauthorized intrusions (Scenario A), supervision of a person who is ill (Scenario B), crime detection (Scenario C) and smoke/fire detection (Scenario D). Each scenario can be characterized by several possible actions and conditions, such as movement detection, object tracking, region limitations, object classification, object size limitations, object feature changes, weather conditions, and work time. The conditions which the system will finally work under are very important. For example, changes in lighting or the appearance of either shadows or reflections in a scene can significantly influence the background model and result in the foreground image being affected by false objects. Therefore, it is crucial to appropriately eliminate false detections in order to extract only the actual object of interest (OOI). Each OOI should be a coherent region of a pre-specified minimum size. More detailed system description is provided in [START_REF] Frejlichowski | SmartMonitor: An Approach to Simple, Intelligent and Affordable Visual Surveillance System[END_REF]. 'SmartMonitor' has been described in [START_REF] Forczmański | Current trends in developing of intelligent visual monitoring systems (in Polish)[END_REF] and [START_REF] Frejlichowski | SmartMonitor: recent progress in the development of an innovative visual surveillance system[END_REF] as well.

In this paper the process of false object removal for the 'SmartMonitor' system is presented. Firstly, it briefly describes the method used for background modelling and foreground extraction, which directly precedes the elimination of falsely detected regions. Additionally, the types of false detections used are summarised. Secondly, the artefacts removal process as applied to two background models using additional operations is described. The paper then presents some experimental results and a concise discussion of them. The database utilized in the process of artefacts removal is very specific and was prepared only for the experiments concerning SmartMonitor system. The final section contains summary and conclusions.

The Process of Background Subtraction and Types of False Detections

The background modelling, foreground localization and artefacts removal processes are elements of the background subtraction process, which is presented as a flowchart in Fig. 1. The first stage, image pre-processing, utilizes algorithms that are mainly for colour conversion or image enhancement and helps facilitate image processing during the subsequent stages. The background models are built adaptively using a Gaussian Mixture Model (GMM), based on various colour components. The foreground image is the result of the subtraction of the background image from a pre-processed video frame. During the data validation stage, the system verifies whether the foreground regions correspond to real or false objects. This is done during the false detection removal process and the final foreground binary mask should only be created for the regions that the system is interested in.

Building an adequate background model is very important since the model influences both the obtained foreground regions and the number of false detections. The background model must be both sensitive enough to localise any real moving objects and sufficiently robust to particular environmental changes in the scene. In this case it cannot be static [START_REF] Horprasert | A robust background subtraction and shadow detection[END_REF] or averaged in time [START_REF] Frejlichowski | Automatic Localisation of Moving Vehicles in Image Sequences Using Morphological Operations[END_REF] because real scenes are very changeable in time. Therefore, the GMM method (e.g. [START_REF] Wang | Modeling Background from Compressed Video[END_REF][START_REF] Piccardi | Background Subtraction Techniques: A Review[END_REF][START_REF] Zivkovic | Improved Adaptive Gaussian Mixture Model for Background Subtraction[END_REF]) has been selected. It allows the adaptive modelling of each pixel as a mixture of Gaussians. This method has been evaluated to be a reliable real-time tracker that can quickly adapt any changes appearing within the scene and can deal with slow variations in illumination and repeated disturbances from unexpected motion in the background clutter [START_REF] Stauffer | Adaptive background mixture models for real-time tracking[END_REF]. Despite the advantages, the method has some drawbacks that are mainly associated with the utilized colour information and the type of the environment which is present in the scene. False detections can take various forms, such as large coherent regions, isolated pixels or small groups consisting of several pixels. The reasons for artefacts occurrence are [START_REF] Javed | A Hierarchical Approach to Robust Background Subtraction Using Color and Gradient Information[END_REF]:

-sudden changes in illumination, that can completely change the background colours and increase the difference between the model and the current frame; -shadows of moving objects, that cause illumination changes and might be classified as foreground regions; -background movements -i.e. the relocation of a part of the background, which causes a change within two regions, namely the newly acquired and previous positions. Both become considered as part of the foreground whereas only the previous position should; -background initialization in the presence of moving objects -moving objects that belong to the foreground are mistakenly incorporated into the background and partly occlude it.

Fig. 2 shows examples of various types of false detections obtained for a background model with 256 grayscale values. Each row contains a sample video frame, a background model and a foreground image respectively. It is evident that the resulting foreground regions are larger than they should be, with the area of each moving object being surrounded by redundant pixels. Fig. 2 illustrates the results of: In summary, the foreground image can include pixels that correspond to both moving objects and false detections. Artefacts can take the form of larger coherent regions, small groups of pixels, or single isolated pixels. False detections are often connected with the actual object of interest, which makes them more difficult to eliminate. Areas of noise can also result from image compression or low data transmission quality.

The Process of Artefacts Removal

For the 'SmartMonitor' system artefacts removal process, three key issues were taken into consideration and needed to be eliminated, namely the influence of a moving object that was visible in the scene during background model initialization, shadow areas and noisy regions. First of all, two separate background models based on the Y component (intensity) of the YIQ colour scheme and the H component (hue) of the HSV colour scheme were built. Various background models (see Fig. 3(a) and Fig. 3(b) for examples) allowed different information about possible ways to simplify the artefacts removal process to be obtained. Moreover, additional operations and modifications were introduced in order to eliminate the aforementioned false detections.

The first problem, i.e. the presence of a moving object in the background model, occurs mainly when a model is initialized using the first frame obtained from the video stream. However, it is often impossible to obtain an image without moving objects in it, especially from busy environments. Therefore, the initial background image pixel values should be random. On the one hand, this will cause the model to require more time to adapt to the current situation of the scene, and on the other, the resultant background image will be more accurate and the influence of moving objects will be reduced.

The next issue is associated with shadow detection and removal. Here, the utilization of two different background models is discussed. It was stated in [START_REF] Stauffer | Adaptive background mixture models for real-time tracking[END_REF] that by building the background model using intensity values it is impossible to distinguish between moving objects and moving shadows. The authors of [START_REF] Kaewtrakulpong | An Improved Adaptive Background Mixture Model for Real-Time Tracking with Shadow Detection[END_REF] proposed the utilization of a colour component to detect moving shadows and to reduce the computation time. According to [START_REF] Forczmański | Surveillance Video Stream Analysis Using Adaptive Background Model and Object Recognition[END_REF], shadows affect only intensity values and not the hue of shaded and open regions to a significant extent. Therefore, the comparison of two different foreground images, obtained using intensity and hue background models, allows for shadow exclusion. Two exemplary foregrounds are illustrated in Fig. 3(c) and Fig. 3(d).

The last problem to be solved is that of the elimination of noisy areas. This is done in two stages and each foreground image is processed separately before shadow exclusion is performed. Firstly, image thresholding is performed in which non-zero pixel values are changed to 1. This results in an image with white foreground areas and a black background. Secondly, two morphological operations are applied -i.e. erosion and dilation. Erosion allows for the elimination of isolated groups of several pixels, hence resulting in reduction of the foreground region. Dilation then fills-in the holes and completes the pixels removed from the object region. Afterwards, the process of shadow elimination takes place. Here, two foreground binary images without noisy areas are multiplied using an entrywise product -i.e. when two pixels of the same coordinates are considered to be part of the foreground, their respective pixel in the final binary mask is white, otherwise, the zero value is assigned. A pictorial representation of the particular stages of the artefacts removal process is shown in Fig. 4. As can be seen from Fig. 4, both the shadow area and the majority of noisy regions were eliminated. The obtained foreground mask contains a moving object shape and several smaller regions that are not taken into consideration since the system only analyses of a pre-specified minimum size.

Experimental Conditions and Results

The experiments were performed using a test database containing a set of video sequences which were suitable for pre-planned system scenarios with specified parameters. The main goal was to investigate the effectiveness of the false object removal process when applied to the 'SmartMonitor' system. Each experiment was carried out in the same way. The background model was first initialized with random pixel values and then iteratively adapted to each subsequently processed frame. The subsequent stages of the background subtraction process for an individual video frame are shown in Fig. 5. foreground binary mask. A sample frame from the video sequence fulfilling the conditions of Scenario A, which shows a person walking in a garden, is depicted in Fig. 6(a). A shadow area was detected in the intensity model (Fig. 6(b)) and the foreground (Fig. 6(c)) was affected by noisy areas resulting from background movements and video compression. However, the moving object shape was extracted as expected (Fig. 6(d)). Fig. 7 shows the results for Scenario B. Here, the sample frame shows a person who fell over and is lying still. Noise and shadow areas were smaller than in the previous example and were completely removed. A similar situation is visible in Fig. 8, which concerns Scenario C, with sample frame presenting a person with hands raised. The moving shadow visible in Fig. 9(a) was also eliminated and so the final binary mask (Fig. 9(d)) does not contain any foreground areas. Experimental results were evaluated visually by the users and showed that the majority of falsely detected objects have been successfully removed. This proves the effectiveness of the false object removal process in application to the 'SmartMonitor' system. There is no available data that could be compared with the results as a ground-truth -the utilized database is very specific and adapted to system scenarios.

Summary and Conclusions

In the paper, the application of the artefacts removal process to the 'SmartMonitor' system was presented. Firstly, it introduced the main characteristics of the system and some basic information about the background subtraction process. The method for eliminating false detections within two background models was then described. Despite the fact that the system is currently under development, some experimental results were also provided and discussed. Different background models allow various foreground images to be obtained. Therefore, we focused on the intensity component of the YIQ colour scheme and the hue component of the HSV colour scheme in order to exclude shadow areas. Moreover, we introduced additional operations and modifications in order to eliminate false detections. These were morphological operations for noise reduction, and the use of an initial background model with random pixel values to decrease the influence of moving objects present during initialization. The experiments showed that the proposed method gave satisfactory results. However, several additional issues, such as camera placement or system sensitivity level, could influence both the number of artefacts and number of false alarms.

Fig. 1 .

 1 Fig. 1. Flowchart of the background subtraction algorithm (based on [10]).

  (a) a sudden illumination change caused by sunrays passing through a window.Other possible causes are: turning the light on and off, a camera flash or changing weather conditions such as a partially cloudy sky with sun shining through the clouds; (b) the appearance of a moving object shadow area; (c) the movement of small background elements, mainly tree leaves and grass.As a result the foreground region is very noisy; (d) model initialization with a frame containing a moving object which occludes part of the background. Because there is no information about the occluded background region, it is considered as part of the foreground.

Fig. 2 .

 2 Fig. 2. Examples of false detections for the intensity model.

Fig. 3 .

 3 Fig. 3. Examples of: (a) an intensity background model, (b) a hue background model, (c) an intensity foreground image and (d) a hue foreground image.

Fig. 4 .

 4 Fig. 4. The illustration of the consecutive steps of the artefact removal process: input image thresholding, erosion, dilation and foreground mask extraction.

Fig. 6 -

 6 Fig. 6-9 present some experimental results for various system working conditions and different environments -i.e. scenes recorded both inside and outside a building, with changing weather or lighting conditions, and background movements present. Each figure contains: (a) a sample frame, (b) a foreground image of the intensity model, (c) a foreground image of the hue model and (d) a

Fig. 5 .

 5 Fig. 5. The diagram of background subtraction process with artefacts removal stages.

Fig. 6 .Fig. 7 .Fig. 8 .Fig. 9 .

 6789 Fig. 6. Exemplary results of the artefacts removal process for scenario A.

Acknowledgements. The project 'Innovative security system based on image analysis -"SmartMonitor" prototype construction' (original title: Budowa prototypu innowacyjnego systemu bezpieczeństwa opartego o analize obrazu -"SmartMonitor") is a project co-founded by the European Union (project number PL: UDA-POIG.01.04.00-32-008/10-01, Value: 9.996.604 PLN, EU contribution: 5.848.800 PLN, realization period: 07.2011-04.2013). European Funds -for the development of an innovative economy (Fundusze Europejskie -dla rozwoju innowacyjnej gospodarki ).


Mirosław Kurkowski
email: mkurkowski@icis.pcz.pl

Olga Siedlecka-Lamch

Paweł Dudek
email: pdudek@icis.pcz.pl

Using Backward Induction Techniques in (Timed) Security Protocols Verification

Keywords:

This paper shows a new way of automatic verification of properties of untimed and timed security protocols. To do this we use a modified version of previously introduced formal model based on a network of synchronized (timed) automata that expreses behaviour and distributed knowledge of users during protocol executions. In our new approach we will use the backward induction method for searching of a tree of all real executions of an investigated protocol. Our approach uses additionally the boolean encoding of constructed structures and SAT solvers for searching answers to the questions about investigated properties which are expressed as reachability or unreachability of undesired states in a considered model. We exemplify all our notions and formalisms on the well known NSPK, and show experimental results for checking authentication and security properties of a few untimed and timed protocols.

Introduction

The modern people process tens of gigabytes of information a day, most of which is transferred electronically. "Consumption" of information is a must, it gives people the knowledge, capabilities, and does not allow to fall outside the margins of society. The transfer of information must remain undisturbed, consistent with reality and not threatened by outside intruders. Such communication should be guaranteed by a number of communication protocols, secured by modern cryptographic techniques. The heart of every communication protocol is a security protocol that meets the following requirements: mutual authentication of communicating entities, confidentiality of transmitted information, integrity of this information and a new key-session distribution.

Security protocols used in practice satisfy one or more of the above requirements using either symmetric or asymmetric cryptography. Many of the developed security protocols proved to be vulnerable to the attack by malicious Intruders [START_REF] Lowe | Breaking and Fixing the Needham-Schroeder Public-key Protocol Using fdr[END_REF][START_REF] Lowe | Some new attacks upon security protocols[END_REF], and investigators undertook the challenge of formal methods of protocol verification.

The process of creating the protocol is difficult, but it seems more difficult to verify. The first step is to create a valid, full formal description. The description should include all parties, states and actions occurring in the protocol: participants (sender and receiver), the information about keys that encrypt the transmitted data, actions of generating, encoding, sending, receiving and decrypting information. The Common Language is a commonly used protocol specification language, which unfortunately does not allow for a full description. It shows only the scheme of sending messages and their construction. In this case there is a need for using more complicated languages, for example presented in the papers [START_REF] Kurkowski | Applying Timed Automata to Model Checking of Security Protocols[END_REF][START_REF] Kurkowski | Verifying Timed Security Protocols via Translation to Timed Automata[END_REF][START_REF] Kurkowski | Verifying Security Protocols Modeled by Networks of Automata[END_REF].

The precisely specified protocol can be automatically verified in many possible ways. The field of automatic verification has been exploited for many years by both academic and commercial institutions. Basically, there are two main ways of verification: testing real and virtual systems (simulations), or modeling and formal verification. Of course after testing the already implemented systems, we can be sure that the system has worked properly only so far. Formal modeling and verification is based on building adequate mathematical structures, showing the actions that occur during the protocol execution. Of course these methods are succesfully used to model and verify various kinds of computer systems. Good examples are [START_REF] Fray | A New Mathematical Model for the Analytical Risk Assessment and Prediction in IT Systems[END_REF][START_REF] Kurkowski | A Propositional Logic for Access Control Policy in Distributed Systems[END_REF]. There are numerous approaches to the verification of security protocols associated sometimes with appropriate tools [START_REF] Amnell | Uppaal -Now, Next, and Future[END_REF][START_REF] Armando | The AVISPA tool for the automated validation of internet security protocols and applications[END_REF][START_REF] Kacprzak | Verics 2007 -a model checker for knowledge and real-time[END_REF][START_REF] Armando | Sat-based model-checking for security protocols analysis[END_REF][START_REF] Corin | Timed model checking of security protocols[END_REF][START_REF] Delzanno | Automatic verification of time sensitive cryptographic protocols[END_REF][START_REF] Evans | Analysing time dependent security properties in CSP using PVS[END_REF][START_REF] Bella | Using Isabelle to prove properties of the kerberos authentication system[END_REF].

The algorithmic approach is based predominantly on model checking, but we can distinguish among formal methods also those inductive [START_REF] Paulson | Inductive analysis of the internet protocol tls[END_REF][START_REF] Bella | Verifying the set registration protocols[END_REF] or deductive [START_REF] Kurkowski | A Propositional Logic for Access Control Policy in Distributed Systems[END_REF][START_REF] Burrows | A logic of authentication[END_REF][START_REF] Kurkowski | A Quantifier-free First-order Knowledge Logic of Authentication[END_REF]. Intuitively, model checking of a protocol proceeds in checking whether a formal model of protocol executions contains an execution or a reachable state that represents an attack upon the protocol. Comparing to standard model checking techniques for communication protocols or for distributed systems, the main difficulty is caused by the need to model the Intruder which is responsible for generating attacks as well as changes of knowledge (about keys, nonces, etc.) of the participants. The Intruder can be modeled in several ways, although the Dolev-Yao model and its versions seems to be the most adequate [START_REF] Dolev | On the security of public key protocols[END_REF]. In mentioned model the Intruder has access to all the transmitted information, can collect and use it with a precision according to its skills and resources, and is able to send it somehow and sometime through the network. Of course, the Intruder does not need to comply with the requirements of using the protocols and, in particular, does not have to use fresh information or to meet time requirements.

Using model checking we face another serious problem -the exponential explosion of states, which depends on the number of participants, sessions, or messages. The model should predict all possible scenarios with a huge amount of information generated and sent by the Intruder. In considered case the computational complexity of model checking algorithms is typically exponential in parameters of the verified protocols, particularly in the number of participants and execution steps. This problem calls for the modification of existing models and algorithms, as well as finding new ones.

So far, our studies in this area were directed at the two models: a network of synchronized automata for modeling separately the executions of a protocol and the knowledge of the participants like in [START_REF] Kurkowski | Applying Timed Automata to Model Checking of Security Protocols[END_REF][START_REF] Kurkowski | Verifying Timed Security Protocols via Translation to Timed Automata[END_REF][START_REF] Kurkowski | Verifying Security Protocols Modeled by Networks of Automata[END_REF] or using the chains of states of protocol execution, see [START_REF] Siedlecka-Lamch | A New Effective Approach for Modeling and Verification of Security Protocols[END_REF]. In the first case, the constructed networks of automata were translated to the propositional boolean formulas. The security property was firstly expressed as a property of reachability of certain global states in the automata network, and subsequently as a satisfiability of the formula. SAT-solver answered the question whether satisfying valuation exists, which was equivalent to the existence of an attack or an undesirable situation. By contrast, if the formula turned out to be unsatisfiable, it meant that no attack exists.

For the searching of models of executions of concurrent systems, the backward induction technique is sometimes used. Generally speaking the method consists in constructing a tree of executions in accordance to the reversed relation to that which determines the dependence between the states in the basic model. In some situations, for example in the case of testing the reachability of certain states, this causes the reduction of size of the constructed trees. In the case of protocols this approach was sucessfully used in a few works, for example in [START_REF] Kurkowski | Using Backward Strategy to the Needham-Schroeder Public Key Protocol Verification[END_REF].

In this article we propose the approach of the backward induction technique for the investigation of properties of protocols by building a network of automata encoding the tree of protocol execution, where the runs take place inversely to the runs proposed in [START_REF] Kurkowski | Applying Timed Automata to Model Checking of Security Protocols[END_REF][START_REF] Kurkowski | Verifying Timed Security Protocols via Translation to Timed Automata[END_REF][START_REF] Kurkowski | Verifying Security Protocols Modeled by Networks of Automata[END_REF]. The automata built in this approach are slightly bigger in size, which is why the experimental results confirm greater efficiency of the proposed approach in the case of protocols with a small number of steps. It is interesting that this method may also be used in the case of time-dependent protocols, and the networks of time automata which model them.

The Needham-Schroeder Public Key Protocol

The designing of the communication protocols is a very hard task which is connected with the possibility of appearing many problems with later use of a made protocol. As the essential example the NSPK protocol can be presented [START_REF] Needham | Using encryption for authentication in large networks of computers[END_REF].

In the notation of this protocol there are designations i(A) and i(B), which express identifiers of the participants of the communication, respectively the A and B participants. The expression X K A means the X message encrypted by the public key of A participant. Similarly, the message encrypted by the public key of B participant -X K B .

The A participant has a very important role -starts the run of the protocol. The aim of the execution of this protocol is to achieve the mutual confirmation of the identity (the authentication) between the communicating participants. The designation A → B : X refers to sending the X message from the A participant to B participant. We assume that sending the message causes the operation of receiving it by the suitable person. The concatenation of the elements in the message was determined by the operator "•".

Example 1. The scheme of NSPK protocol proposed in [START_REF] Needham | Using encryption for authentication in large networks of computers[END_REF] is as follows:

α 1 A → B : N A • i(A) K B , α 2 B → A : N A • N B K A , α 3 A → B : N B K B .
The A participant in first step of the protocol execution generates the random number (nonce) N A and sends it to the B participant with A's identifier encrypted by the public key of the B user. The next step of protocol execution starts from generating by the B participant its own random number N B . Next it creates the message consisting of random numbers of both communicating participants, encrypts this message by the public key of the A participant and sends it to the A. In the next stage of the execution, A runs decrypting operation of the received message and the operation of comparing the N A number, which got from B with the number N A , which was prepared by him. If both numbers are equal, A considers B as authenticated. In the last step of the protocol execution A sends to B its random number N B encrypted by the K B key. After decrypting and comparing the proper numbers, the B participant can consider the A participant as authenticated. This protocol execution should guarantee both participants the identity of the communicating persons.

Example 2. Figure 1 presents the automata based model of honest execution of NSPK Protocol due to formal definitions from [START_REF] Kurkowski | Applying Timed Automata to Model Checking of Security Protocols[END_REF][START_REF] Kurkowski | Verifying Timed Security Protocols via Translation to Timed Automata[END_REF][START_REF] Kurkowski | Verifying Security Protocols Modeled by Networks of Automata[END_REF]. In the presented networks synchronisation of component automata is used, it consists in the fact that the global transition (in the network) labeled by the label α is enabled, if in all components if there exists transitions labeled by α, then at least one of them in each automaton is enable. It is assumed further that all states are accepting ones. As it can be seen the model consists of automata modeling the execution of external actions of the protocol (sending messages) A and automata that model distributed knowledge of participants

(A A N A , A A N B , A B N A , A B N B ).
For example, the automaton A A N A models the knowledge of the user A about the random number N A . Executions of additional actions constituting the protocol are represented by labels on automata transitions. Transitions labeled by α 1 model execution of the first step of the protocol. During execution of that step, users A and B acquire knowledge about the number N A . Transitions labeled α 2 model the performance of the second action of the protocol, in which users gain knowledge about the number N B . We should pay attention on the loop in automata A B N A , labeled also by α 2 , it models the condition to possess knowledge about number N A by B, to execute the second step of the protocol. Accordingly, the transitions labeled α 3 , model the execution of the third step of the protocol. The NSPK protocol was used through 17 years. In 1995 Gavin Lowe discovered the version of the protocol execution which consisted a possible attack, showing that the NSPK protocol is susceptible to a break-in [START_REF] Lowe | Breaking and Fixing the Needham-Schroeder Public-key Protocol Using fdr[END_REF]. The Intruder is the additional participant with its own identifier and the keys, determined by ι symbol. The Intruder does not do the protocol according to the scheme but uses own ways, impersonates other users and cheats them.

A q i f s 0 1 ? α 1 i f s 1 1 ? α 2 i f s 2 1 ? α 3 i f s 3 1 A A N A i f q ? α 1 r 0 1 i f r 1 1 α 2 6 A A N B i f q ? α 2 r 0 2 i f r 1 2 α 3 6 A B N A i f q ? α 1 r 0 1 i f r 1 1 α 2 6 A B N B i f q ? α 2 r 0 2 i f r 1 2 α 3 6
Example 3. The attack presented by Gavin Lowe is as follows:

α 1 1 A → ι : N A • i(A) K ι , α 2 1 ι(A) → B : N A • i(A) K B , α 2 2 B → ι(A) : N A • N B K A , α 1 2 ι → A : N A • N B K A , α 1 3 A → ι : N B K ι , α 2 3 ι(A) → B : N B K B .
The Lowe scheme shows two simultaneously NSPK protocol executions. The α 1 execution refers to the communication between the A participant and the Intruder. The α 2 execution refers to the situation where the Intruder pretends to be the A participant and in his name communicates with B. To have correct protocol which cannot be broken it is enough to add the identifier of the sender to sent message in the second step of the original NSPK protocol execution:

N A • N B • i(B) K A .
All known verification methods and tools confirm safety of this version of NSPK.

Backward induction in modeling and verification of untimed protocols

As mentioned earlier, in the verification of systems modeled by transitional structures, backward induction is sometimes used. This takes place when there is hope that it is easier to build an execution tree of a program or system by constructing it, so to say, from the end, moving backwards from a certain state in accordance to a specific relation of a passage in the structure. Examples indicate that sometimes this method is very efficient, especially in the case of stating unreachability of certain states (see [START_REF] Kurkowski | Using Backward Strategy to the Needham-Schroeder Public Key Protocol Verification[END_REF]).

In order to verify security protocols using the backward induction method, we will now define the product automaton which models inversely the runs which take place in the product automaton constructed in previous sections. An appropriate theorem of the adequacy of the calculations done in both product automata will allow the searching of the tree using the backward induction method.

Let A be a family of automata A i , i ∈ I meeting the following conditions. Let A i = {Q i , Σ i , δ i , s 0 i , F i } be an automaton, where:

-Q i = {s 0 i , s 1 i , . . . , s t i }, for all i ∈ I and some t ∈ N is the set of states of automata A i , -Σ i = {k 1 i , k 2 i , . . . , k s i } is the set of labels, where (Σ i ∩ Σ j = ∅, dla i j) for all automata from A, -δ i ⊆ Q i × Σ i × Q i is a transition relation that meets the following conditions: • (s l i , k, s j i ) ∈ δ i iff l = j -1, for any l = 0, 1, . . . , s -1 oraz j = 1, 2, . . . , s, • if (s l i , k, s l+1 i ) ∈ δ i and (s p i , k, s p+1 i ) ∈ δ i , then l = p. -s 0 i is an initial state, F i = Q i is the set of finite states.
It is noticeable that this family defines the automata which have the same structure as automata modeling the execution of protocols defined in [START_REF] Kurkowski | Verifying Security Protocols Modeled by Networks of Automata[END_REF][START_REF] Kurkowski | Verifying Timed Security Protocols via Translation to Timed Automata[END_REF][START_REF] Kurkowski | Applying Timed Automata to Model Checking of Security Protocols[END_REF]. The following conditions have been met:

the sets of states of all the automata are equally numerous.

the relation of the passage in each automaton is determined only on a pair of states directly following one another. labels do not duplicate in different automata, nor do they duplicate within the scope of one automaton, all states of the automata are accepting ones.

We denote by Σ the set of all labels from automata from the family A (Σ = i∈I Σ i ). Now the family of automata corresponding to the knowledge automata will be defined.

Let B be a family of automata B j , j ∈ J that meets the following conditions. B j = {R j , Σ, ρ j , r 0 j , T j } where:

-R j = {r 0 j , r 1 j }, for all j ∈ J, -Σ is the set of labels constructed before, -ρ j ⊆ R j × Σ × R j is the transition relation that meets the condition: (r l j , k, r p j ) ∈ ρ j iff l = 0 ∧ p = 1 or l = p = 1, r 0 j is an initial state, T j = R j is a set of finite states. It is noticeable here that these automata have the same structure as knowledge automata constructed in the previous section:

each have two states, transitions are defined only from the first state to the second, and from the second state to itself, labels are taken from the set of all labels from the automata of the A family, all states are accepting ones.

By AB we denote the product automaton (network of automata) defined over the family A ∪ B due to definition of product automaton given in [START_REF] Kurkowski | Verifying Security Protocols Modeled by Networks of Automata[END_REF].

We will now define the product automaton modeling the runs of automaton AB executed inversely.

For all automata A i ∈ A let A i be a smallest automaton that meets the following conditions:

A i = {Q i , Σ i , δ i , s t i , {s t i , s 0 i }} where:

-δ i ⊆ Q i × Σ i × Q i is a transition relation that meets the condition: if (s l i , k, s l+1 i ) ∈ δ i , then (s l+1 i , k, s l i ) ∈ δ i and (s l+1 i , k, s 0 i ) ∈ δ i . -s t
i is an initial state, {s t i , s 0 i } is a set of accepting states. One should notice that the sets of states and labels are the same as in corresponding automata of the family A. By A we define the family of all such constructed automata.

Moreover for all automata B j ∈ B we define automata B j as the smallest automata that meet for every j ∈ J:

B j = {R j , Σ, ρ j , r 2 j , {r 0 j , r 2 j }} where:

-R j = R j ∪ {r 2 j } = {r 0 j , r 1 j , r 2 j }, -Σ is the set of labels constructed before, -ρ j ⊆ R j × Σ × R j is the transition relation that meets the following conditions: if (r l j , k, r p j ) ∈ ρ j , then (r p j , k, r l j ) ∈ ρ j and (r 2 j , k, r l j ) ∈ ρ j . r 2 j is an initial state, {r 0 j , r 2 j } is a set of accepting states.

By B we denote the family of all automata constructed before.

Example 4. Figures 2 and3 present the intuition of the constructions implemented above. According to the above mentioned definitions of the beginning states of automata A, B 1 , B 2 are accordingly: s 0 1 , r 0 1 , r 0 2 , whereas accepting ones are all states of the automata. In the case of automata A, B 1 , B 2 , beginning states are accordingly: s 3 1 , r 2 1 , r 2 2 , whereas accepting ones are states s 3 1 , s 0 1 , r 2 1 , r 0 1 , r 2 2 , r 0 2 . One should notice that in the first network runs over the words: q 1 , q 1 q 2 and q 1 q 2 q 4 exist. In the second product automaton there are accordingly runs over the words: q 1 , q 2 q 1 and q 4 q 2 q 1 .

A 1 i f q s 0 1 ? q 1 i f s 1 1 ? q 2 , q 3 i f s 2 1 ? q 4 i f s 3 1 B 1 i f q ? q 1 r 0 1 i f r 1 1 q 2 6 B 2 i f q ? q 2 r 0 2 i f r 1 2 q 4 6 Fig. 2. Direct automata model A 1 i f s 0 1 6 q 1 q 1 i s 1 1 6 q 2 , q 3 q 2 q 3 i s 2 1 6 - @ - q 4 i f q s 3 1 B 1 i f 6 q 1 r 0 1 i r 1 1 q 2 i f q J J J J J J ] H H H Y r 2 1 q 2 q 1 6 B 2 i f 6 q 2 r 0 2 i r 1 2 q 4 i f q J J J J J J ] H H H Y r 2 2 q 4 q 2 6
Fig. 3. Reverse automata model One can see from the previous example that suitable accepting runs exist in the product automaton of the first type only if in the product automaton of the second type exist accepting runs which are mirror-reversed. The suitable example of network of automata that models reverse execution of NSPK is presented in Example 5.

Example 5. Figure 4 show the reverse automata model for execution of NSPK Protocol given in Example 2. As done so previously, let's consider the product automaton AB. For such constructed families of automata the following theorem holds.

A i f s 0 1 6 α 1 α 1 i s 1 1 6 α 2 α 2 i s 2 1 6 - @ - α 3 i f q s 3 1 A A N A i f 6 α 1 r 0 1 i r 1 1 α 2 i f q J J J J J J ] H H H Y r 2 1 α 2 α 1 6 A A N B i f 6 α 2 r 0 2 i r 1 2 α 3 i q f J J J J J J ] H H H Y r 2 2 α 3 α 2 6 A B N A i f 6 α 1 r 0 1 i r 1 1 α 2 i q f J J J J J J ] H H H Y r 2 1 α 2 α 1 6 A B N B i f 6 α 2 r 0 1 i r 1 1 α 3 i q f J J J J J J ] H H H Y r 2 1 α 3 α 2 6
Theorem 1. In the product automaton AB there exists the run over the word q = q 1 , q 2 , . . . , q w iff in the product automaton AB there exists the run over the word q = q w , . . . , q 2 , q 1 . Proof of Theorem 1 proceeds by induction considering the length of the word q. Proof of the right implication. In order to prove the inductive base, one should notice that if in product automaton AB there exists a run over the word q = q 1 , then there exists exactly one automaton from the family A in which the transition labelled q 1 is the transition from the beginning state to its successor. Therefore it is fulfilled that for a given i ∈ I we have (s 0 i , q 1 , s 1 i ) ∈ δ i . According to the definition of the automaton AB in automaton A i there exists the transition (s t i , q 1 , s 0 i ) ∈ δ i . It is noticeable that according to the definitions of knowledge automaton from the family AB, in which any transition is labelled with label q 1 , then there also exists an appropriate transition labelled q 1 leading from the beginning state r 2 j to state r 0 j . For automata where in their transitions the label q 1 does not appear, an apropriate definition of ending states of the product automaton AB should be reminded.

In order to prove the inductive step, it is assumed that the right implication is true for words of length k, therefore it is true that if in the product automaton AB there is a run over the word q = q 1 , q 2 , . . . , q k , then in the product automaton AB there is a run over the word q = q k , . . . , q 2 , q 1 . It now should be proved that the implication is true for words of length k + 1.

Any given word q = q 1 , q 2 , . . . , q k , q k+1 should now be considered. According to the definition of the product automaton AB there exists exactly one automaton from the family A in which there exists a transition labelled q k+1 . So it is fulfilled that for a given i ∈ I, (s j i , q k+1 , s j+1 i ) ∈ δ i . According to the definition of automaton AB in automaton A i there exists a transition (s t i , q 1 , s j i ) ∈ δ i . It is also noticeable that according to definitions of knowledge automata from the family AB, in which any transition is labelled with label q k+1 , there also exists an appropriate transition labelled q k+1 . Proof of left implication is analogous.

It should also be noticed that the same property concerns the accepting runs. The reason for this results directly from the above statement and in the definition of accepting states of the components of families of both types.

Backward induction in modeling and verification of timed protocols

Just like in the previous section, a model automata of time-dependent protocol executions which allows verification using the backward induction method will now be presented. Because the knowledge automata in this chapter do not include time aspects, only the construction of timed automata representing protocol execution will be introduced. Let C be a set of time constraints defined in [START_REF] Kurkowski | Applying Timed Automata to Model Checking of Security Protocols[END_REF][START_REF] Kurkowski | Verifying Timed Security Protocols via Translation to Timed Automata[END_REF]. Aditionally let TA be a family of timed automata T A i (i ∈ I for some indices from I) that meet the following conditions.

Let T A i = {Q i , Σ i , δ i , s 0 i , F i , X i } be a timed automaton, where:

let Q i = {s 0 i , s 1 i , . . . , s t i }, for all i ∈ I and some t ∈ N be a set of states in A i , let Σ i = {k 1 i , k 2 i , . . . , k s i } be the set of labels where A (Σ i ∩ Σ j = ∅, dla i j),

-δ i ⊆ Q i × Σ i × C × 2 X i × Q i be
a transition relation that satisfies:

• (s l i , k, cc, X, s j i ) ∈ δ i iff l = j -1, for all l = 0, 1, . . . , s -1 and j = 1, 2, . . . , s,

• if (s l i , k, cc, X, s l+1 i ) ∈ δ i and (s p i , k, cc, X, s p+1 i ) ∈ δ i , then l = p. -s 0 i is an initial state, -F i = Q i is the set of accepting states, -X i is the set of clocks.
This family defines automata which have the same structure as those defined in [START_REF] Kurkowski | Applying Timed Automata to Model Checking of Security Protocols[END_REF][START_REF] Kurkowski | Verifying Timed Security Protocols via Translation to Timed Automata[END_REF] timed automata modeling the execution of time-dependent protocols. A timed automaton modeling reverse protocol execution will now be constructed.

For each automaton T A i ∈ A let T A i be a smallest automaton that satisfies the following conditions:

A i = {Q i , Σ i , δ i , s t i , {s t i , s 0 i }, X i } where:

-δ i ⊆ Q i ×Σ i ×C×2 X i ×Q i be a transition relation that satisfies: if (s l i , k, cc, X, s l+1 i ) ∈ δ i , then (s l+1 i , k, cc, X, s l i ) ∈ δ i and (s l+1 i , k, cc, X, s 0 i ) ∈ δ i . -s t
i is an initial state, -{s t i , s 0 i } is a set of accepting states. In the case presented below, there holds a proper and adequate theorem concerning the existence of accepting runs in product automata including families execution automata as well as knowledge automata. The proof is analogous like in the previous one. For it should be noticed that only execution automata include nonempty time constraints, and these are accordingly modeled in a reverse product automata.

Experimental results

In this section the results of experiments performed according to methodology discussed above will be presented and described. The results were obtained with the original implementation done in C++. For testing we used untimed and timed versions of four of well known protocols: NSPK (mentioned above), Lowe's version of NSPK (NSPKL), Wide Mouth Frog (WMF), and CCITT. The implementation generates for a given (in ProToc language [START_REF] Kurkowski | Verifying Security Protocols Modeled by Networks of Automata[END_REF][START_REF] Kurkowski | Verifying Timed Security Protocols via Translation to Timed Automata[END_REF]) protocol and defined in it the space of considerations, different interpretations -executions of the tested protocol. These executions, in turn, are automatically translated to the network of untimed or timed automata. Then automata are translated to the boolean propositional formula in CNF (conjunction normal form) format. Formulas are optimized and tested using SAT-solver MiniSAT. The existence of a valuation satisfying the formula is equivalent to the existence of an attack on the protocol. Lack of satisfying valuation shows that there was no attack in the considered finite space. The module enables testing the previously described attacks. The performed calculations found the known attacks upon protocols. The tables presented below mainly focus on verification parameters: memory used by the CPU and computation time.

The verification method that uses the backward induction approach gave better results in the case of the WMF and CCITT protocols in both cases of untimed and timed versions. This may be caused by a small number of protocol steps, resulting in slight differences in the constructed model and the size of the formula. In the case of protocols with a larger number of steps automata model was a little biger and encoding gave larger formula. In this case searching by the solver took a bit more time than in the direct method.

Table 1 and 2 show a comparison of the direct verification and the backward induction technique in the case of untimed and time dependent protocols. After conducting a series of calculations for these protocols and their analyzis, the following conclusions can be made: the backward induction method gave somewhat better results in the case of protocols with a small number of steps. In the case of long protocols the method did not quicken obtained verification results.

Summary

Research carried out by various international teams show that there is no single, "ideal" method of verification for all protocols. Often we must select the method for the given protocol. During the searching for the next models and methods we developed and implemented the backward induction method for constructing automata that model executions of security protocols. After a series of computation and their analysis we can draw the following conclusions: the backward induction method in the case of automata based modeling of executions and verification of security protocols due to methodology given in [START_REF] Kurkowski | Verifying Security Protocols Modeled by Networks of Automata[END_REF][START_REF] Kurkowski | Verifying Timed Security Protocols via Translation to Timed Automata[END_REF] may give better results only in the case of protocols with a small number of steps and there it can be successfully used. For long protocol method does not speed up the computations.

Fig. 1 .

 1 Fig. 1. Automata model of execution of the NSPK Protocol

Fig. 4 .

 4 Fig. 4. Reverse automata model for NSPK execution

Table 1 .

 1 Comparison of direct and backward methods of untimed protocols verification

		Direct	Direct	Backward Backward
	Protocol Memory (MB) Time (s.) Memory (MB) Time (s.)
	WMF Untimed	8,56	0,004	7,78	0,002
	CCITT Untimed	9,13	0,041	8,84	0,031
	NSPK	9,57	0,102	13,5	0,137
	NSPKL	11,3	0,156	15,61	0,171

Table 2 .

 2 Comparison of direct and backward methods for time dependent protocols

		Direct	Direct	Backward Backward
	Protocol Memory (MB) Time (s.) Memory (MB) Time (s.)
	WMF	10,32	0,004	9,41	0,002
	CCITT	10,89	0,063	10,24	0,045
	NSPK T imed	11,56	0,110	16,32	0,166
	NSPKL T imed	13,72	0,210	18,77	0,231

The second and the third author acknowledge support from EU Project (European Social Fund.) PO KL Information technologies: Research and their interdisciplinary applications,


Seiji Sugiyama
email: seijisan@is.ritsumei.ac.jp

Atsushi Ikuta
email: a.ikuta@sch.otani.ac.jp

Daisuke Yokozawa
email: dyokozawa@gmail.com

Miyuki Shibata

Tohru Matsuura

Displaying Genealogy with Adoptions and Multiple Remarriages Using the WHIteBasE

Keywords: Adoptions, Multiple Remarriages, Hidden Node, Segment Intersections, Search Algorithm, Free Layout

In this research, needs of displaying genealogy with various family relations are described and those solutions using our WHIteBasE method are proposed. Previous WHIteBasE method has perfectly been able to integrate each relation that includes a married couple and their children, and has been able to display complex relations with segment intersections easily. It has also been added that Genealogy with Direct Segments (DS), Genealogy with Hooked Segments (HS) and Annotation Data Always Displayed (ADAD). In this paper, two new functions are added to the WHIteBasE method. One is 'Genealogy with Adoptions'. Using 'Adopted Segments (AS)', not only biological family relations but also social family relations can be displayed simultaneously. The other is 'Genealogy with Multiple Remarriages'. Using 'Double Bends (DB)', crossing relations more than 3x3 both sexes can be displayed perfectly. Our improved software that can display AS and DB automatically and seamlessly by only mouse operation is presented.

Introduction

There is a requirement to display complex relations in family trees. However, it cannot be displayed perfectly in existing genealogy display software [START_REF] Sugito | Alliance[END_REF]- [20]. When complex relations are inputted in the software, one individual is often displayed in multiple places automatically. It is thought that almost all of them consider only simple family trees and have no idea to display complex layout. As a result, users must reconstruct the scattered individual placements into only one relation in their mind, though it is graphical display software. On the other hand, 3D graphics is rather more difficult to understand complex relations than 2D because many names and segments overlap [START_REF] Naito | Topic Map for Displaying Genealogy[END_REF]. GEDCOM [START_REF]GEDCOM LETTER[END_REF], a de facto standard for recording genealogy data exchange format, is not enough to display complex relations because it considers no layout information. New software has been constructed in our research so that it can display complex relations [START_REF] Sugiyama | A Study of An Event Oriented Data Management Method for Displaying Genealogy: Widespread Hands to InTErconnect BASic Elements (WHIteBasE)[END_REF]. Our software uses an event oriented data management method, "WHIteBasE" (Widespread Hands to InTErconnect BASic Elements). It is a hidden node for integrating relations that include a married couple and their children. If WHIteBasE is used, one individual can be displayed only once because complex relations with segment intersections can be displayed. Intuitive inputs and inspections such as map image display systems can be realized.

In our previous software, the regular Japanese layout style has been used as shown in Fig. 1. It includes a double horizontal segment MS (Marriage Segment), a vertical segment TS (Trunk Segment), a horizontal segment BSS (Brothers and Sisters Segment), and a vertical segment BS (Branch Segment). The '△' denotes a male and the '⃝' denotes a female that are a couple connected by using MS. Children are connected from the intermediate of MS by using TS, BSS and BS.

Fig. 2 shows our previous software [START_REF] Sugiyama | Displaying Genealogy with Various Layouts by using the "WHIteBasE" Method[END_REF]. It has been constructed by using not only 'Regular Layout' as shown in Fig. 3 In this paper, needs of two more different family relations are described and those solutions are proposed. One is 'Genealogy with Adoptions' such as shown in Fig. 11 [START_REF]Nerva-Antonine dynasty[END_REF]. Not only 'Biological Relations' showing solid segments but also 'Social Family Relations' such as adoptions showing dashed segments are often written simultaneously. It is necessary to display these dashed segments named 'Adopted Segments (AS)' for connecting adoptions. Connections of AS from parent(s) to a child/children have three types as the following: On the other hand, connections of AS from parent(s) to a child/children in HS have three types as the following: The (A)-(C) and (a)-(c) are similar to DS and HS respectively (Fig. 345678). If all descendants in a family are adoptions, the difference is only a change of segment types from solid segments to dashed segments. On the other hand, if a family has children including both biological relations and adoptions, the segment type of TS becomes the solid segment, and both solid segments and dashed segments are used on the way to the children as shown in Figs. 18(a)-(f). If there are two families, one is biological relations and the other is adoptions, and/or if there is a connection from one of brothers and sisters to others, both solid segments and dashed segments in HS are used as shown in Figs. 18(g)-(i).

The other is 'Genealogy with Multiple Remarriages' such as mating of the racehorses shown in Fig. [START_REF]WeRelate[END_REF]. In this case, a bloodline is important. As a result, there is a case that relations including only several horses grow very powerful, because of focusing on a strong horse. Connections of remarriages have two types as the following: Closed areas cause crossing of MS (Fig. 19). In our previous research, no crossing of MS has been considered, and the horizontal MS style has been only defined.

To cope with the difficulty, 'Double Bends (DB)' for crossing of MS is added. In this research, an upgrade, adding two kinds of family relations that use AS and DB to our previous genealogy display software by using the WHIteBasE method, is proposed. Our improved software that can also display AS and DB automatically and seamlessly by only mouse operations is presented.

WHIteBasE

In this section, the WHIteBasE method that is our previous proposal [START_REF] Sugiyama | A Study of An Event Oriented Data Management Method for Displaying Genealogy: Widespread Hands to InTErconnect BASic Elements (WHIteBasE)[END_REF][24] is briefly introduced. A relation between a married couple and their child is managed as an event by a Hidden Node, WHIteBasE as shown in Fig. 25(a). The connection model using WHIteBasE is shown in Fig. 25(b). WHIteBasE has three keyholes, S L , S R (Substance) and D (Descendant). Individuals have two keys, A (Ascendant) and M (Marriage). A can connect with D, and M can connect with S L or S R , where denote one family.

For plural children as shown in Fig. 26(a), D is extended in multiple keyholes D j as shown in Fig. 26(b). For multiple marriages as shown in Fig. 27(a), M is extended in multiple keys M k (Fig. 27(b)) and plural WHIteBasEs are used. That can define all of biological relations perfectly.

A set of W i that defines WHIteBasEs and a set of I j that defines Individual Nodes are represented by

W i = {S L , S R , D j , Q} I j = {A, M k }    i = 0, 1, • • • , i max j = 0, 1, • • • , j max k = 0, 1, • • • , k max (1)
where i, j, k denote IDs on the data table respectively, i max , j max , k max are the maximum values, S L , S R denote IDs of a couple, D j denotes ID of descendants, A denotes ID of an ascendant WHIteBasE, and M k denotes ID of WHIteBasEs for handling marriages. Individuals are managed by using data table including names and annotation data. WHIteBasEs are managed by using data table separated from Individuals. Remarriages are managed by using plural WHIteBasEs. Q denotes a set of coordinate values of each position managed by a WHIteBasE measured from the origin of the displaying area (Fig. 28) and is represented by Q = {q b , q L , q R , q d , q aj , q cj , q tl , q rb } .

(

) 2
where q b denotes a WHIteBasE's position, q L , q R denote the parents' positions, q d denotes a junction's position between MS and TS, q cj denotes children's positions, q aj denotes junctions' positions between BSS and BS, q tl , q rb denote positions of top-left and bottom-right of all area managed by a WHIteBasE. One of advantages using WHIteBasE is the decreased reference volume. Using the existing software, all of individuals connect with other individuals (Fig. 29(a)). On the other hand, using the WHIteBasE method, two reference links per a child decrease (Fig. 29(b)). Moreover, the user can understand the complex relations intuitively and can input and inspect them easily. Using segment intersections is necessary for displaying complex relations. If only one WHIteBasE is used, there is no segment intersections. On the other hand, if plural WHIteBasEs are used and horizontal segments (MS, BSS) and vertical segments (TS, BS) are displayed, the positions of segment intersections can be calculated by using only four patterns of line crossing as the following:

(a) MS of W α and TS of W β are crossing (Fig. 30(a)) The four patterns are only calculated while only two WHIteBasEs' management rectangle q tl , q rb are overlapped. Therefore, this search method is faster than checking all segments. Genealogy with Direct Segments (DS) is necessary for connecting parent(s) and their child directly. DS from a Single Parent is used while WHIteBasE lies under a parent (Fig. 31(a)). DS from Parents is used while WHIteBasE overlapped one of parents (Fig. 31(b)). Two kinds of DS are automatically switched according to the positions only (Fig. 31(c)) without changing the connection model [START_REF] Sugiyama | Displaying Genealogy with Various Layouts by using the "WHIteBasE" Method[END_REF]. Genealogy with Hooked segment (HS) is necessary for connecting parents and their children in parallel layouts. BSS as shown in Fig. 1 is extended to three parts; BSS l , BSS v , and BSS h (Fig. 32(a)). For calculating HS, positions q vl , q vh are added to Eq. ( 2). Occurring HS is automatically switched according to the positions only (Fig. 32(b)) [START_REF] Sugiyama | Displaying Genealogy with Various Layouts by using the "WHIteBasE" Method[END_REF].

If x α,L < x β,b < x α,R & y β,b < y α,b < y β,d , the intersection is (x β,b , y α,b ). (b) MS of W α and BS of W β are crossing (Fig. 30(b)) If x α,L < x β,cj < x α,R & y β,aj < y α,b < y β,
The search method of segment intersections for DS and HS has been proposed in our previous paper [START_REF] Sugiyama | Displaying Genealogy with Various Layouts by using the "WHIteBasE" Method[END_REF]. Therefore, the figures of search patterns are omitted in this paper. Only nine search patterns are used for DS and HS because there are three horizontal segments and three vertical segments. Consider the arc style of segment intersections in the case of using AS. It is necessary to use arcs on the intersection between solid horizontal segments and solid vertical segments as shown in Fig. 34(a). It can be displayed to use arcs on the intersection between solid horizontal segments and dashed vertical segments as shown in Fig. 34(b). However, the dashed segments are broken up if arcs are used in the intersection between dashed horizontal segments and dashed vertical segments as shown in Fig. 34(c). In addition, it is difficult to display arcs in the narrow area, especially near the area connecting with AS as shown in Fig. 35. Therefore, it is useful that no arcs is used for crossing by using AS as shown in Figs. 34(d)-(g).

The search method of segment intersections for AS is very simple because AS has no arcs. Classify only solid segment sections and dashed segment sections as shown in Figs. 36(a),(b). Then, search the segment intersections for only solid sections. The connecting points of AS on the top of Individual text box is line up in order to locate WHIteBasE's horizontal positions as shown in Fig. 36(c).

Genealogy with Multiple Remarriages

'Double Bend (DB)' is necessary for displaying multiple remarriages more than 3x3 partners in 2D. Therefore, MS is extended as shown in Fig. 37. In this case, define that MS denotes the section that WHIteBasE exists, MS v denotes the vertical section, and MS h denotes the horizontal section that no WHIteBasE exists. For calculating DB, positions q m , q e are added to Eq. ( 2). Finally, Q is represented by Q = {q b , q L , q R , q d , q aj , q cj , q vl , q vh , q m , q e , q tl , q rb } .

(

For seamless mouse operations, set the movable range between WHIteBasE and Individual as shown in Fig. 38. When mouse drag vertically in the movable range, MS becomes DB. MS h can be arbitrarily set both upper side and lower side. In the first dragging operation, the bending positions occurs at the center between WHIteBasE an Individual. After that, MS v can be arbitrarily moved by using mouse drag operation on the section from WHIteBasE to Individual. If MS h approaches MS, DB return to MS automatically.

WHIteBasE only exists on the section MS when DB is used. Therefore, the connection styles of children from DB have only four patterns as shown in Figs. 39. Provided that DB and BSS do not overlap.

The intersection style of DB, that is, crossing between double horizontal segments and double vertical segments, has not been defined in custom. Therefore, some crossing styles can be thought such as shown in Figs. 40(a)-(d). For simple viewing, Fig. 40(d) is used in this research.

Search Method of Segment intersections

Using not only regular layout but also AS and DB, there are four horizontal segments and four vertical segments. The positions of segment intersections can be calculated by using only 16 patterns of line crossing as the following: 9 mid denotes q vl or q vh , min denotes q vl , and max denotes q vh . respectively with segment intersections. Only changing from solid segments to dashed segments can realize adoptions display by using not only regular layout but also DS and HS. Using DB can realize multiple remarriages display. A lot of individuals with complex relations including adoptions could be displayed in narrow area using one window. Even if the client area is filled, scrolling mouse wheel, the zoom rate can be changed and displaying area beyond the window size can be used. Using our method, genealogy required in a favorite rectangle size can be displayed easily. Even if AS and DB are used, segment intersections could be displayed automatically and seamlessly by only mouse operation.

Conclusion

In this research, Genealogy with Adoptions and Multiple Remarriages could be constructed by using the WHIteBasE method. Future research will be conducted to construct automated layouts, generation search, thinned-out individuals, grid layouts, improving GUI, etc.

Fig. 1 . 2 . 5 .Fig. 6 .Fig. 7 .Fig. 8 .Fig. 9 .Fig. 10 .

 125678910 Fig. 1. Segment Names for Japanese Regular Layout Fig. 2. Our Previous Software [24]

Fig. 11 .Fig. 15 .Fig. 16 .Fig. 17 .Fig. 18 .

 1115161718 Fig. 11. Sample of Genealogy with Adoptions[START_REF]Nerva-Antonine dynasty[END_REF]

(

  A) AS from MS: One married couple is connected with a child/children from the intermediate of MS as shown in Figs. 12(a),(b). (B) AS from a Single Parent: Only a single parent is connected with a child/children directly without using MS as shown in Figs. 13(a),(b). (C) AS from Parents: Only a single parent that has the other parent using MS is connected with a child/children directly as shown in Figs. 14(a),(b).

Fig. 19 .Fig. 21 .

 1921 Fig. 19. Sample of Multiple Remarriages [26]

  (I) Regular Remarriages: A married person marries again after her husband or his wife has died or after being divorced as shown in Fig. 20(a). In this case, there is no closed areas by MS and individuals' text boxes. (II) Multiple Remarriages: All persons of plural couples marry again by replacing each other as shown in Fig. 20(b). In this case, there are closed areas.

Fig. 21 (Fig. 24 .

 2124 Fig. 22. Connections 2x2

Fig. 25 .Fig. 26 .FigFig. 30 .

 252630 Fig. 25. Connection for a married couple and a child

Fig. 32 .

 32 Fig. 31. Genealogy with Direct Segments

  cj , the intersection is (x β,cj , y α,b ). (c) BSS of W α and TS of W β are crossing (Fig. 30(c)) If x α,a1 < x β,b < x α,aj max & y β,b < y α,d < y β,d , the intersection is (x β,b , y α,d ). (d) BSS of W α and BS of W β are crossing (Fig. 30(d)) If x α,a1 < x β,cj < x α,aj max & y β,aj < y α,d < y β,cj , the intersection is (x β,cj , y α,d ).

Fig. 33 .Fig. 34 .Fig. 36 .

 333436 Fig. 33. Connection Model for Genealogy with Adoptions

Fig. 37 .Fig. 40 .

 3740 Fig. 37. Names for Double Bend Fig. 38. ON/OFF for Double Bend

Fig. 41 .

 41 Fig. 41. Search Pattern of segment intersections including Double Bend

Fig. 42 .

 42 Fig. 42. Our New Genealogy Display Software