Introduction The Internet of Things is the future

The Internet of Things is the future of the internet and the future is here. However,

current infrastructure is a thing of the past and building stable and reliable infrastructure

for future IoT systems necessitates consideration of the rapid growth in the number of

connected IoT devices. According to estimates, by the year 2025 the number of connected

IoT devices will be 75 billion [1] and produce about 79 zettabytes of data every day [2].

Further estimates indicate that by 2030 the number of connected devices will reach 125

billion [3].

The information systems currently in use cannot adequately process and transfer to

the cloud the huge amount of data generated by this growth. Systems are further

compromised by the limitations and restrictions on bandwidth. The rise in the number of

IoT devices will create more sensitive and real-time IoT usage in connected car technologies,

real-time production line monitoring, health monitoring, and video conferencing and further

compromise data processing in an inadequate infrastructure. These applications need low-

latency and location awareness for optimal operations [4]. The cloud and internet

infrastructure and resources, in their current form, are simply incapable of managing the

huge amount of data produced by this growth in the internet of things [5].

1.1 Fog Computing

To address these issues and the inadequacies of cloud computing, there is need for a

new, more e↵ective platform. Fog computing is one platform that can be used to manage the

IoT. Fog computing is a virtualization architecture that handles fundamental distinguishing

services closer to the ground. Fog computing can process large amounts of data, handle

storage, and networking services, and handle real-time acquisition and location awareness [6,

7]. Fog computing improves privacy and data security as data is stored and processed close to

end users at the base of the network, between the devices and the cloud [8, 9].

1.2 Characteristics of Fog Computing

There are many characteristics of fog computing that are making it more popular in the

field of technology, particularly in light of the IoT expansion. It is an upgrade on cloud

computing with more features that are useful for new technological challenges.

Fog computing supports cloud computing and allows analytics resources to conduct

intensive and extended term analytics [10]. Fog computing is close to the user, at the edge of

the network thus ensuring low latency and e cient services, a characteristic critical to

applications such as interactive sessions, networked games, healthcare applications, and video

streaming which require low latency and location awareness.

Another indication of the benefits of fog computing is the geographical spread and high

number of fog nodes. These are set to support moving vehicles and other mobile applications

Fog computing provides a critical foundation for the new innovations in autonomous vehicles,

ensuring quality services in connected cars technologies.

Fog computing, at the edge of the cloud and geographically spread, will prove to be

beneficial in increasing bandwidth e ciency while improving data privacy. In fog computing

data is processed at the fog node which means the need to send large amounts of data to the

cloud is significantly reduced thus minimizing the consumption of bandwidth and maximizing

the privacy of data because sensitive information will not be transmitted [6, 8, 9].

1.3 Fog Computing in Healthcare Systems

There are numerous challenges facing worldwide healthcare systems [11, 12]. Fog

computing capabilities can help address these challenges. Inadequacies in current systems

render the use of cloud computing technology in many current healthcare applications

ineffective. For instance, the transmission of data from the sensors to the cloud and from the

cloud to hospitals is slow on cloud computing. This is specifically important as healthcare

systems often require urgent on-the-fly, responses that command data processing to increase

e ciency. Slow data transmission compromises the e ciency of healthcare systems. [13].

Further healthcare data is sensitive and protected by the Health Insurance Portability

and Accountability Act of 1996 (HIPAA) [14, 15] so the minimization of data transfer supports

and guarantees data security. For this very reason, healthcare providers often prefer data

storage remain within the organization. This increase in e ciency for both patient and provider

is impetus for healthcare systems to adopt fog computing [16].

Fog computing is also used by some [17] to pre-process data before it is transmitted to

the cloud initiating faster response to patient needs. To take advantage of fog computing, [18]

introduced a novel hierarchical computing architecture for IoT-based patient monitoring

systems targeted at the execution of machine-learning data analytics. [19] utilized fog

computing technology to collect data traces on patient movement so that patients can access

faster and more e cient services, at low latency, in the event of a medical emergency.

Fog computing is increasingly applied in the healthcare industry, attracting the

attention of many healthcare technology researchers as will be discussed in Chapter 2. One of

the most important issues in both fog computing and healthcare is the preservation of data

security and the privacy of end users of the system and patients. There are numerous studies

that strive to address the security issues of fog computing in a healthcare setting [20], but there

are still aspects of this issue that need further attention, such as assessment of data damaged

by malicious attacks and determination of a method of secure data recovery after it has been

damaged by malicious transactions.

1.4 Fog Computing in Critical Infrastructure Systems

Fog computing in smart city utilities, will enable the IoT and smart devices to process

data faster, setting up quicker decision making and saving time. This also means the

aggregation of data will be limited to the indispensable data in the cloud. The processing of

huge amounts of data is required in smart cities and many countries around the world

developing these cities, fog computing has compelling potential for the processing of. smart

meters, tra c data, city activities, and utilities data and. E ciently processed data will

accommodate sustainable living in very developed cities [21]. However, it is important to note

that it would be unrealistic to rely entirely on fog computing for processing large volumes of

data. Cloud computing will necessarily continue to be used in the e↵orts to ensure successful

smart cities.

Fog computing can be used by service providers and utility to manage and analyse

consumer data e ciently, ensuring customers access to improved services. Many research

studies exist on increasing the e↵ectiveness of fog computing in smart cities and solving

technical issues arising in the processing of volumes of data, especially those that require

integration to the cloud [22]. IoT devices like smart meters in modern smart cities will not only

generate a lot of data but the diversity of that data will have to be processed in realtime [23].

While data in large quantity is generally very valuable, archaic technology will not harness the

full value of data collected in smart cities. The current cloud is insu cient for handle such

amount of data, especially tasks like processing the aggregate data, analysis and storage [24]

and while data security and privacy issues have been documented by researchers, damage

assessment and data recovery in the event of a cyberattack continue to require study and

innovation.

1.5 Intelligent Environment Systems (Governments as example)

Governments around the world are focusing on intelligent environmental systems

aimed at both conserving the environment and improving the lives of humans. Fog computing

makes it possible to build these systems and optimize the benefits of environmental systems

including provision of high-quality services. Still, there are risks involved in developing

intelligent environmental or government systems. Perhaps the worst of those risks are data

protection and data recovery in the event of a data breach.

In fact, one of the major concerns as regards government system data is the sensitivity

of that data; any data breach could expose the country to attack from enemy states or

terrorists. [25]. Some of the sensitive data domiciled in intelligent government systems include

tra c control systems, video-conference applications, and real-time surveillance camera

monitoring, and they require real-time processing and location awareness. Therefore, data

damage assessment and recovery are essential in preventing data breaches as well as building

a secure and dependable database. In a government data environment, the transmission of

crucial data is common and needs to occur in a safe system secure from intrusion. For instance,

an attack on a tra c control system or real-time surveillance camera monitoring application

would paralyze their vital functions like real-time processing and location awareness. The

repercussions of damaged government data systems may include destruction of property or

even loss of life and manipulation of economic systems. So, in addition to developing

appropriate mechanisms for adaptation of fog computing in intelligent systems, developing

adequate security features capable of responding to attacks by providing fast and accurate

damage assessment and recovery techniques is of cardinal importance.

1.6 Computing System Security

Securing a computing system is critical in every situation and industry. There are three

key phases required to ensure a system is protected and secure. The first phase is data

protection. Techniques like access control, encryption, auditing, and authentication are

applied to the system to secure and protect the data. The second phase is an intrusion and

compromise detection system This can be software or a device that monitors the system with

the goal of sensing any malicious activities or policy violations and raising an alarm so that it

can be addressed. The most vital component of this phase is timely detection and notification

of the system compromise [26]. This phase uses an Intrusion Detection System (IDS) which

can observe system activity and alerts the person who is in charge of any unusual activity. This

requires more assistance from the third phase, which includes damage assessment and data

recovery ensuring the integrity and accessibility of the data in the system.

The third phase is critical in detecting any further transgressions on the system and

making sure that the database has been restored and is secure. This phase can be divided into

two important stages: damage assessment and data recovery. Damage assessment is the

primary process in this phase and is used to identify compromised transactions and data

items. Data recovery restores the damaged data to its last consistent state before the attack. To

make this possible, log files must retain information about the changes applied to data items

by various transactions in the system [27].

Delay time is computed in the damage assessment stage from the moment the IDS

identifies a malicious transaction until all transactions or data items a↵ected by the

introduction of the malicious transaction have been identified. During this time, the system

will be unavailable so, we aim to minimize the this process requires as much as possible. Time

latency for the data recovery stage is computed from the moment all a↵ected transactions have

been received until all data items have been recovered. During this time only the a↵ected data

items will be unavailable for use so as before, we aim to minimize the time required for this

process.

The system is not capable of assessing all damaged data through the damage

assessment and data recovery algorithms with the use of log files on each fog node

independently in a fog computing environment. For instance, as shown in Fig. 1.1, if the

Intrusion Detection System (IDS) identifies T3 in Fog1 and T8 in Fog2 as malicious transactions

and if every involved fog node individually tests their local log files, the system will then just

detect T5 and T6 as a↵ected transactions in Fog1 and T10 as an a↵ected transaction in Fog2.

However, T7 and T8 in Fog3, dependent on the a↵ected transactions in Fog1, and T9 in Fog2,

dependent on the a↵ected transactions in Fog3, have been a↵ected and will not be detected by

these independent assessments. So to confirm that all a↵ected transactions in the system are

detected there must be collaboration between fog nodes.

Figure 1.1: An example of the necessity of having cooperation between fog nodes to obtain

accurate data damage assessment. L notation could indicate any possible operation.

1.7 Summary of Contributions

Securing any computing system is necessary for the protection and security of the

system and its data. To that end, three primary phases are essential to ensure a system is

protected and secure [27]. The first phase in data protection utilizes methods including access

control, auditing, authentication, and encryption. The second phase focuses on intrusion

detection and utilizes software or a device that observes the system with the intent of detecting

any malicious activity or policy violations. If intrusion of the system occurs, the third phase,

which includes damage assessment and data recovery, ensures the integrity and availability of

system data. This third phase is essential in detecting any additional data corruption and in

ensuring the system is returned to a secure state.

The main objective of this research is to demonstrate the ability of the proposed

algorithms to detect data damaged in an attack in systems maintaining extremely sensitive

databases and employing fog computing environments. Critical infrastructure systems, smart

cities, intelligent government systems, and healthcare systems are among those where

databases store sensitive information. They are prime targets for attacks.

The first goal of this research is the construct of two models for fog computing based

on healthcare systems. The first architecture will use fog modules with heterogeneous data,

and the second will use fog modules with homogeneous data. A unique approach to damage

assessment will be proposed for each module.

Traditional damage assessment and data recovery algorithms usually delete data

affected by an attack to guarantee the integrity of the database. In the proposed algorithms the

a↵ected data will be identified and retained for use in any future investigation. Suppose, for

instance, a critical patient information system was attacked. A treating physician, unaware of

the data violation, administers medication to a patient with life-threatening allergies.

Identifying, and retaining the original, a↵ected data has the potential to avoid further

consequences.

The second goal is to introduce a unique model that uses fog computing to manage

utility service companies and consumer data in the infrastructure systems of smart cities. A

novel technique to detect and assess data items that are a↵ected by a malignant attack will be

proposed. This proposal will generate a method for recovery of the original data and a strategy

for returning the database to a state consistent with that prior to the transgression. The

construct of a damage audit table, a structure, that will be used to collect data needed in the

recovery process, will be implemented.

The third goal of this research is to design a novel model for an intelligent government

system that will use fog computing technology to control and manage the data in the entire

system. Unique algorithms that will sustain the integrity of data in the system in the event of a

cyberattack, are proposed for this segment of the research. These algorithms are intended to

maintain the security of systems experiencing the execution of a malicious transaction or

modified data in the database of fog node. A transaction dependency graph will be

implemented in this model to observe and monitor all transactions and quickly detect all

a↵ected transactions if a malicious transaction is found.

2 Literature Review

2.1 Fog Computing

The benefits of cloud computing are synonymous to its advantages especially to

businesses and other related entities. One such benefit revolves around the reduction of

workload as well as the administrative burden of system maintenance and data management.

Work is made easier, cheaper, and fast with cloud computing. The need for low latency,

mobility support, and geo-distribution and location awareness must be addressed with the

changing needs of database management [6]. This development pushed for the

implementation of a new infrastructure by Cisco Systems known as fog computing in 2014.

Bonomi et al. [28] advised that fog computing is just an addition or an enhancement on cloud

computing technologies that are central to edge computing technologies to handle issues

facing the computing system such as high latency and inflexibility.

Fog computing as a computing infrastructure has elicited the attention of the

academia and other interests such as for industrial research [29, 30, 31, 32]. Several

researchers developed architecture models for the fog system as discussed in Section [33,

34] in general survey or study of the challenges, issues, and future direction.

2.1.1 Fog Computing Features

Fog computing has been known to advance the features of cloud computing to

improve database operations. The first feature associated with fog computing concerns

location,

which can be termed as the edge of networks. This feature enhances the quality of services

provided that are high and reduces the latency from high to low, a factor that helps save time

and system performances. Application areas include the healthcare industry through the

monitoring applications used for patients, gaming, and online streaming of videos. Mobility is

a substantial feature in fog computing that is promoted through the broad dispersion of fog

nodes, hence enhancing its geographical accessibility. An example of the applicability of these

characteristics is in moving vehicle services. This application makes fog a vital keystone in the

provision of high-quality services for associated car technologies. Fog’s feature of being

located at the edge of the cloud and its widespread geographical distribution help increase

bandwidth e ciency, privacy, and security of sensitive data. Most of the local data in a database

system are processed by fog nodes, which indicates that a reduction in the amount of data sent

to the cloud for processing will help reduce the consumption of bandwidth.

This activity ensures the maximization of privacy related to sensitive data transmission [6, 8].

Therefore, fog computing should work as a proper, appropriate platform for numerous

sensitive Internet of Things (IoT) services and applications, which could include connected

vehicles, electricity automation systems, and smart cities.

In their study regarding the present direction of patterns for technology usage and the

development of enabling technologies, Vaquero et al. [35] proposed a comprehensive

definition of fog computing, that is, “a scenario in which a large number of heterogeneous

ubiquitous and decentralized devices communicate and there exists potential cooperation

among themselves and with the network to complete storage and processing tasks without

third party intervention. They further provided an explanation for why a subscribed

communication model is required when data only requires to be sent or published. This helps

reduce tra c in the network, keep congestion problems at the edge of the network, and have a

positive influence on privacy protection.”

The importance of preprocessing whereby data gets changed and the movement of data

to the cloud utilizing computing technologies such as smart gateway was discussed by Aazam

et al. [17]. They devised a new infrastructure for smart gateway, which was mainly concerned

with smart homes and would enable the connection to IoT devices. They also proposed a new

architecture for a smart gateway using fog computing. Ivan et al. [36] investigated the merits

of fog computing for services in various dimensions. The services include electricity networks,

IoT, CPS, and automation of buildings. They studied an updated model for fog computing and

its security issues.

2.1.2 Fog Computing Security and Privacy Issues

Cloud computing may not help resolve security and privacy issues, such as data

protection, data availability, authentication, and user communication, leaving the role to fog

computing [37]. The combination of crucial data enhances privacy and security because most

of the data are processed locally at the edge of the network [38]. Security is enhanced as the

distance of the data sent is minimized, making fog computing systems advantageous. The local

processing and minimization of that distance minimizes the transmission of sensitive data

over the network, hence reducing the susceptibility to eavesdropping [39]. Several security

and privacy issues can be mitigated by integrating fog computing with IoT infrastructure

[40].

However, security and privacy issues have largely contributed to the research and

contributions of novel concepts and improvement solutions [37, 41, 42]. The utilization of fog

computing in smart grids, cities, and intelligent systems such as healthcare and government

systems to enhance the quality of services provided, and supply security and privacy to

consumers has also attracted the attention of researchers [43, 44, 45, 46, 36, 47, 48].

A fog computing architecture was mentioned in [49], in which the cloud and IoT have

to be provided with end-to-end security. Fog computing architecture relies on fog nodes

responsible for managing data and providing communication services in the system. The fog

node design should encompass functional security measures to provide reliable security and

protection, and achieve a dependable end-to-end computing infrastructure. The establishment

of trusted fog nodes means that a safe network can be placed on top of the node infrastructure.

This method leads to the formation of a basis for security between one node and another, a

node to a thing, and finally the connection between a node and a cloud.

Zhu et al. proposed a scheme for enhancing privacy by using methods such as blind

signature that would ensure anonymity in the authentication processes using the set

conditions in the system [44]. Billing problems in smart cities would be resolved by their

recommended encryption methods to aggregate smart meter readings in the cloud. This model

has its discrepancies that subject customer data to susceptibility to insider and electronic

attacks.

Lyu et al. also addressed the element of smart cities and smart meter readings [45] by

suggesting a new framework for aggregating smart meter reading safely through fog nodes to

the cloud. The proposed framework involves the addition of statistical noise that is simply

irregularities in the data to enhance the data privacy of their clients. The specific technique

applied here is the Gaussian noise technique to enable the encryption of data and attain

customer privacy.

Mohammed et al. [50], provided an encryption-based scheme to avert rogue fog

computing nodes and stop them from risking end-user data security while upholding reduced

time latency and communication overhead between the cloud and the fog nodes. They also

proposed a blockchain-encryption-based scheme integrating the CP-ABE algorithm with

blockchain technology for the detection of rogue fog nodes federated with other fog nodes.

When rogue fog nodes are detected, they are ousted, making them incapable of accessing data

encrypted with the fog federation’s attributes; data stored in fog nodes in the same federation

or in the cloud are made safe from the rogue. They also relied on blockchain technology to

perform authorization in a distributed manner and track the encrypted data through fog

federations [51].

2.1.3 Fog Computing Architecture in Critical Infrastructure and Intelligent System

Fog computing has been widely applied in the healthcare industry, which has attracted

the attention of numerous researchers [11, 18]. Azimi et al.[18] presented a new hierarchical

computing architecture of monitoring systems for patients based on IoT to benefit from fog

and cloud computing by facilitating the partitioning and executing machine learning data

analytics. A gateway, which acts as a bridging point between the sensor infrastructure network

and the Internet, is needed for the IoT-based healthcare systems to work e↵ectively according

to Amir et al. [19]. To achieve all these, sensor nodes have been utilized to collect data traces

on patient movement, utilizing body area networks that are transferred using fog gateways

that help provide quick services in medical emergency situations at low latency.

Akrivopoulos et al. [11] designed a smart-phone-based application that would help

gather ECG signals from the patient, where the smartphone would act as a fog node. In this

case, the patient has maximal control over his health data and can distribute the information

to his doctors for health status monitoring purposes. Vora et al. [52] devised a new structure

of using fog computing to monitor patients for ambient assisted living.

Vijayakumar et al. [53] described the use of fog computing in the detection and

prevention of diseases such as mosquito-borne illnesses. This application was achieved

through smart wearable devices or sensors that collect information that are later analyzed and

shared through fog computing. Vijayakumar et al. recommended a fog-based health

monitoring and risk assessment system that can be applied to di↵erentiate mosquito-borne

diseases and create alerts whenever an emergency arises. This system comprises a cyber

space, where data processing is undertaken, and a physical space, which contains the user’s

information and environmental factors.

Smart cities and grids have been encompassed and have relied on fog computing to be

adopted e↵ectively. Naranjo et al. [54] devised a new architecture for the utilization of fog

computing in smart cities. The recommended architecture can run the applications on IoT

devices jointly for functions such as computing, routing, and communicating with one another

through the smart city environment. This architecture decreases latency, and improves the

provision of energy and the e ciency of services among things with diverse

capabilities.

Tang et al. [55] also made provisions that smart cities would require a new computing

paradigm to drive IoT services and applications. They recommended a hierarchical distributed

fog computing architecture to allow or support the incorporation of numerous infrastructure

constituents and services in forthcoming smart cities.

To advance the smart city concept, Amaxilatis et al. [56] developed an application for

smart water metering that would supply data in real time such as consumption on demand as

well as bidirectional to end users from metering devices. This application enhances the

infrastructure in the concept of smart cities through fog computing.

Aazam et al. [46] discussed the architecture of industrial IoT, which can be described

as the use of the IoT in the manufacturing industry for applications such as smart sensors,

actuators, and robots. Finally, smart homes have been on the rise according to Froiz et al. [57]

owing to technological advancements such as fog computing, which assists in the development

of IoT applications. Technologies such as WiFi and ZigBee need to be used for these smart

homes to communicate with IoT nodes as well as the cloud. Fog computing must be a solution

that provides essential support closer to the end users to ensure local, real-time processing for

sensitive, complex tasks.

A distributed fog computing architecture coordinator was proposed in [58] for IoT

applications in the smart grid. The key objective of this fog computing coordinator is to

occasionally collect information of fog computing nodes, such as information on the remaining

resources and tasks. Job management is also achieved through the fog computing coordinator

such that all computing nodes can work together on complex tasks. A programming model for

fog- based architecture was also proposed. The introduction of fog node coordination is the

major di↵erence between their proposed architecture and the traditional one. Fog node

coordination aims to enhance the collaboration among fog nodes to meet di↵erent

requirements in the smart grid.

2.2 Database Security

A computing system needs to be secured to guarantee the protection and security of

the system and its data. Database security does not only comprise the technical aspects but

also moral and ethical as well as legal issues, in which specific laws exist to help regulate

information disclosure according to Pernul [59]. The three principles of database security can

be described as secrecy, integrity, and availability of stored data. To achieve this objective, three

primary phases are essential to ensure that a system is protected and secure [27]. The first

phase applied in the protection of data relies on methods such as access control, auditing,

authentication, and encryption. This first phase involves data that are at rest and not moving.

Security is provided for such data including limiting access at entry and endpoints. Access

control of data also involves password management or classification of sensitive data.

The second phase relevant to the protection of data emphasizes the detection of

intrusion and relies on devices that assess the system to detect any malicious activity or policy

violations. Forms of intrusion include misuse of authority such as theft of media or

modification of data, logical inference and aggregation that concerns the sensitivity of data,

masquerade that involves unauthorized access by an intruder masquerading to be an

authorized user, or even bypassing of controls such as passwords, browsing, or through Trojan

horses according to Pernul [59]. This second phase involves data that are in transit. In this

phase, the security of the system borders as well the monitoring of the movement of data and

identifying threats are ensured.

In the case of system intrusion, the third phase, which includes damage assessment

and data recovery, safeguards the integrity and availability of the system data. This third stage

is critical in the detection of any additional data corruption and ensuring that the system

reverts to a secure state. This phase involves data that are already being utilized. Detection

encompasses user monitoring for those who have access to sensitive data.

This research objectively demonstrates the ability of the proposed algorithms in the

detection of system data that are damaged in an attack while maintaining very sensitive

databases and applying fog computing environments. Critical infrastructure systems, smart

cities, intelligent government systems, and healthcare systems are vulnerable to attacks

because of the sensitivity of the information stored in their databases.

2.2.1 Damage Assessment and Data Recovery

Research has studied damage assessment and data recovery in traditional databases.

Models and mechanisms for data recovery following cyberattacks have been proposed [60, 61,

62, 63, 64]. However, academic contribution to damage assessment and data recovery in

modern database infrastructure, such as fog and edge computing, appears lacking. Damage is

usually caused by elements such as computer viruses, Trojan horses, logic bombs, or trap

doors. Recovery can be termed as rolling back of transactions to revert the database to its

previous normal state. This approach should be undertaken immediately after databases are

a↵ected to reduce denial of service as well as ensure the accuracy of the algorithms on

databases in question. Kaddoura et al. [65] recommended the use of a single matrix for damage

assessment and recovery of algorithms. Other techniques such as parsing of the database log

to check for the a↵ected transactions were recommended by [66]. Damage assessment usually

takes place after the set preventive measures fail to prevent malicious attacks. Malicious

attacks generally intend to damage data stored on the database system. Damage can occur to

the whole system of specific objects that are di cult to detect according to Liu at el. [67].

Panda at el. [60] recommended the data dependency method instead of transaction

dependency. Every read and write operation of a transaction must be classified into one of five

di↵erent types grounded on the data dependency between each operation. A directed graph,

whose function is characterized by o↵ering up data items that have been a↵ected in the

database, is utilized.

The column dependency-based approach presented by Chakraborty et al. [68] deduces

the relationship between transactions to determine which transactions a↵ected by malicious

attacks need to be recovered. In this approach, the recovery of data after attacks, which is

usually time consuming, takes less time than traditional approaches. Chakraborty et al.

suggested a recovery method that would take the a↵ected transactions as input and implement

the recovery in two stages: compensation and re-execution. They deduced from their

experiments that when malicious transactions increase in the database, the second stage of

their recovery scheme also increases.

Liu and Yu [67] intended to advance the e ciency of damage assessment and repair in

distributed database systems. First, they identified the challenges and complications faced by

those systems. Then, they proposed an algorithm for distributed damage assessment and

repair. A local damage assessment and recovery (DAR) was adopted on each site. Later, they

adopted an Executor to scan the local log to detect and clean any sub transaction a↵ected by a

malicious transaction. Additionally, a local DAR Manager on each site cooperates with the

Executor to guarantee global coordination between all sites on the system through the

generation of a coordinator for any cleaning transaction.

Panda et al. [69] used the data dependency-based approach to assess the damage that

could occur from electronic attacks and then return the database to a consistent state. They

introduced two algorithms. In the first one, damage assessment and recovery algorithms are

e↵ected simultaneously, resulting in considerable delays due to blocking the system until the

whole procedure is complete. The second algorithm handles this because the system will be

soon available after all the a↵ected and damaged data are identified and blocked. Fu et al. [61]

introduced new dependencies that relied on analyzing inter transaction dependency

relationships to resolve damage assessment. They proposed and evaluated four di↵erent

dependency relationships between transactions that could transfer the damage.

Ammann et al. [66] also introduced algorithm sets and recommended a mechanism

that would only work on the damaged portions of the database to restore the log files

immediately when proposed damage is assessed and perform data recovery algorithms. These

algorithms can only operate while the database is available during repair, but the database

must be unavailable during repair especially when the initial algorithm is performing. This

approach also o↵ers o✏ine analysis of databases and how the process provides data for the

repair of damaged transactions.

In [63], approaches were o↵ered by the authors for data recovery that is maliciously

attacked through the addition of Before-Image Tables (BI Tables). These BI Tables cannot be

modified by any user at any point or time and have values of all deleted and updated data items.

The old value from the BI Tables is rolled back whenever the system detects an update to a

data item made by a malicious attacker. They claimed that this approach can trace the data as

they spread through di↵erent machines. The BI Tables are utilized to repair the damaged data

without even assessing the log file.

Zuo and Panda [70] consequently introduced two dissimilar methods for the detection

of a↵ected transactions in the distributed database system. The first method utilized the peer-

to-peer model, which is much useful when assessing a single point of failure, rather than

multiple failure points in the system. The second method is a centralized model whose e ciency

is high in the case of a large-scale distributed database system as a result of the minimization

of network communications among the sites.

Haraty et al. [65] proposed an algorithm that would track transactions that read from

one another and then keep this information in a single matrix. The advantage of this approach

is that time is not wasted, and recovery is fast, unlike the traditional methods that would roll

back all transactions up to the end. The use of a single 2D matrix helps store dependencies

between transactions by identifying the a↵ected segment of the database.

Additionally, Sobhan and Panda [71] recommended a new logging protocol that records

all the necessary information for the full repair of a database that is updated by committed but

a↵ected transactions. Lala and Panda [72] devised a damage assessment model as well as four

associated data structures to hasten accurate data recovery. These rely on dependency

relationships among the transactions, which in turn update the database. Similar sentiments

or recommendations were echoed by Panda and Zhou [73] to devise accurate, fast methods for

damage assessment. Two approaches, which include the use of transaction dependency

relationships to determine the a↵ected transactions, were recommended in the attacked

database. The other second approach considers data dependency relationships to identify the

data items a↵ected by the attack for future use in terms of

recovery.

The most targeted sites for attacks are those that contain sensitive information such as

E-government sites. In the case of a malicious attacks, such sites require fast damage

assessment as well as recovery of data. Kurra et al. [74] recommended a model that could

advance damage assessment and recovery through minimal log access using multiple agents,

which helps save time.

Rao and Patel in [62] introduced a methodology for data recovery based on the

inclusion of application specific metadata to form transaction dependencies. For the best

performance, a column-based transaction dependency is used in this method. Their model

restores only a↵ected transactions and skips malicious transactions and valid transactions.

2.2.2 Data Dependency versus Transaction Dependency

A collection of operations or tasks, such as reading and writing, can be termed as a

transaction. Every operation has limits, such as minimum processing units that cannot be

further divided. Whenever a data item is written by a transaction, it is possible for it to be read

by another transaction. This situation creates a dependency between those two transactions.

For example, transaction Tx reads data item D1 and then writes data item D2. Similarly, Ty reads

item D2, making transaction Ty dependent on Tx. Owing to this form of dependency, if Tx

becomes a↵ected by a malicious attack, Ty will also be a↵ected. Thus, in a fog computing

environment, a data item that is informed by any transaction in a fog node can be read by any

other.

Therefore, damage assessment relies on either data dependency or transaction

dependency. Data dependency assesses if data items in the database are written after reading

data items that are a↵ected by an intrusion. By contrast, transaction dependency situates a

transaction that is most likely to be a↵ected if a data item that is to be read is written by a

malicious of an a↵ected transaction according to Haraty et al. [65]. In the study of Panda and

Yalamanchili [75], transaction dependency focuses on malicious transactions for system

recovery. Transactions a↵ected by malicious transactions are also placed in line for recovery.

These transactions that are malicious of those that are dependent on them are usually undone.

Others that are a↵ected by malicious transactions are redone. Untouched transactions have

nothing done to them because they are neither dependent on malicious transactions nor

a↵ected by them. Transaction dependency is a self-healing system according to Xia et al. [76].

Consequently, data dependency has all the data items a↵ected by malicious transactions

returned to their previous state that could be the values of the data. Therefore, data

dependency methods for database recovery undo and redo the a↵ected operations or rather

transactions, and do not undo all the transactions according to Zheng [77].

2.2.3 Flushing the Data

Fog computing is known to have storage limitations, and this calls for the periodic

flushing and removal of data and corresponding log files of fog nodes and their permanent

storage in the cloud [29, 78]. Each fog node, therefore, will have e cient and automated access

to its own cloud space. In specific cases, further assessment of the flushed data needs to be

undertaken using the proposed algorithm. However, assumptions are made that this action

will be executed at optimal intervals when the proposed approach has been launched and all

a↵ected transactions detected or the IDS has provided clearance to the flushed data.

The advantages of this [29] are its capability to enhance the runtime e ciency of the

proposed algorithm because the size of the fog database used in our approach is likely to be

diminished. Another advantage is the improved e cacy in detecting a↵ected transactions

among all data that is flushed to the cloud because all the data will be in one high-performance

machine. Flushing is, however, meant to be performed when the database is in a secure state

and the commitment of all transaction is complete.

3 Ensuring Data Integrity in Fog Computing Based Healthcare Systems

Model

Some of the following paragraphs, figures, and algorithms that will be introduced in

this chapter have been already published in our work [43] as shown in the publications and

reprint permissions chapter 7.

3.1 Introduction

The future of the internet will be in the Internet of things (IoT), which is evidenced

by the significant increase in wearable technology, smart homes and buildings, connected

vehicles, and smart grids. The estimated number of connected IoT devices in 2030 is nearly

125 billion, which will produce an enormous amount of data [3]. Due to the limitation and

restriction of bandwidth, as well as the rapid growth in the amount of data produced, the

current information system architecture will be inadequate for managing and moving that

volume of data to the cloud. In many scenarios, it could be impractical to do so, especially

with the increasing number of IoT devices in use. Additionally, our current society has

incorporated a lot of sensitive and real-time applications of IoT as integral parts of our lives

for instance, through the use of connected car technologies, video conference applications,

health monitoring, and real-time production line monitoring, all applications requiring

lowlatency and location awareness in order to provide satiable and high-quality services [4].

The need for a new platform will become necessary to address the above-mentioned

issues. For that purpose, fog computing, introduced by Cisco, is a virtualization architec-

ture that provides many fundamental distinguishing services close to the ground, including

the ability to process copious amounts of data, storage, and networking services, making fog

computing especially appropriate for many sensitive applications that require real-time

acquisition and location awareness [6]. It enhances privacy and security because the data is

kept and computed close to end users at the edge of the network, between the end devices and

a cloud [8].

Fog computing has several unique characteristics that will not only establish it as an

extension of the cloud, but will also provide extra privileges over the cloud. The first feature is

its location at the edge of networks, providing end users with high-quality services and low

latency. Many current applications require location awareness and low latency to provide a

higher quality of services and performances, such as healthcare applications, networked

games, video streaming, and interactive sessions. Another essential characteristic is the widely

dispersed and significant numbers of fog nodes that will be geographically available, a design

that supports mobility in many applications, including service in moving vehicles. This will

make fog an important cornerstone of providing high-quality services for connected car

technologies. Both fog’s location at the edge of the cloud and its geographically widespread

distribution will also contribute to the benefits of increasing bandwidth e ciency and

enhancing the privacy and security of sensitive data. Most of the data will be processed locally

at the fog node, meaning that the amount of data needing to be sent to the cloud for processing

will be diminished, helping to minimize bandwidth consumption and maximize the privacy of

transmitting sensitive data [6, 8].

The healthcare system faces several challenges [11, 12] that some features of fog

computing mentioned above may be able to solve. Therefore, the healthcare system can

capitalize on fog computing to create better experiences and services for both patients and

providers. One of the most crucial issues in both the fields of fog computing and healthcare is

preserving the security and privacy of consumer or patient data. While several studies have

sought to solve the security issues of fog computing in a healthcare environment [20], there

are still aspects of this issue that should be given further attention, such as assessment of the

damage data could su↵er from malicious attacks and determination of how to securely recover

data from malicious transactions. Damage assessment and data recovery are essential in

creating secure and reliable databases, particularly for the transmission of sensitive data, such

as that of the healthcare environment. For example, if an intrusion detection system (IDS)

detects malicious transactions in the system, any other transactions that read this data will

also be a↵ected, resulting in any doctor’s decision made based on a↵ected transactions,

potentially putting a patient in danger of harm. To the best of our knowledge, there has been

no previous work done on the development of damage assessment and data recovery methods

for fog computing systems. We present two models for using fog computing systems that

manage healthcare data: architecture using fog modules with heterogeneous data, and a

second architecture using fog modules with homogeneous data, using unique approaches for

each module for assessing the damage caused by malicious transactions, for accurately

recovering data, and for identifying a↵ected transactions for future investigation.

3.2 The Models

In this section, we introduce two possible architectures for using fog computing to

manage healthcare data. For each architecture, we propose suitable algorithms to determine

the e↵ect of an attack on the system and identify data damaged either directly or indirectly so

that they can be recovered quickly. We assume in both cases that the intrusion detection

system (IDS) is responsible for detecting the malicious transactions in the system and will

provide a list of these transactions. In addition, each fog node in both architectures must have

its own log file. Both architectures proposed here also use a strict serializable history, and the

log files cannot be modified by users at any time.

3.3 Model Notations

Table 3.1 shows the description of notation to be used in our proposed approaches.

Table 3.1: Notation used in our proposed approaches description.

Notation

Description

FDR

The main fog node, which is accessed by the health care

providers to read and write about the patients.

Fog node for specific monitors used to collect the data from

the patients using the IoT devices, e.g. Fog of Heart Monitors.

MT L

List of detected malicious transactions done by IDS.

A↵ Lfdr

List of all a↵ected transactions that have been detected in

FDR.

A↵ Lfdrj

List of all a↵ected transactions that have been read by FDR

from FMj.

A↵ Lfmj

List of all a↵ected transactions that are detected by the

proposed algorithm in the fog node FMj.

A↵ Lfdrcloud

List of all a↵ected transactions that done by cloud over the

flushed data of FDR fog node.

A↵ Lfdrcloud,j

List of all a↵ected transactions that done by cloud over the

flushed data of fog node j and have been read by FDR node.

A↵ Lcloud,j

List of all a↵ected transactions that done by cloud over the

flushed data of fog node j.

3.4 The First Proposed Architecture: Fog Nodes with Homogeneous Data

In this model, data will be written to one fog node, which can be read by multiple fog

nodes. The patient data will be collected using end-users and Internet of things (IoT) devices,

such as sensors, and sent to the proper fog node, which we call fog monitors (FM). For example,

information about a patient’s heart rate will be sent to the Fog of Heart Monitors, and his or

her blood pressure reading will be sent to the fog of blood pressure monitors. Therefore, each

fog node FM will contain only homogeneous data.

Additionally, in this model there is a main fog node, known as the Fog for Doctor

Reports (FDR), which has access to read any necessary data from the other fog nodes (FMs).

Healthcare providers, however, will only have access to the main node. When a doctor wants

to check patient records, he or she must read the patient’s data from the FDR and write reports,

concerns, and prescriptions based on that data, as shown in Fig. 3.1. We assume that each fog

node will have the ability to perform some basic operations with the data, such as calculating

a patient’s average body temperature over a certain time frame or aggregating the totals of

selected data values.

3.4.1 Damage Assessment Algorithm for the First Model.

Once the IDS detects all malicious transactions in the system, it will send to each fog

node a list of malicious transactions that have been detected on it. Let us say that a malicious

transaction Ti has been detected by the IDS on Fog1. Fog1 will then perform the following

procedures:

Figure 3.1: First proposed architecture “fog nodes with homogeneous data”.

3.4.1.1 First procedure:

Fog1 will check its local log to confirm whether Ti is still in its local database (DB).

• If Ti is not in the DB, it has been flushed to the permanent storage in the cloud.

In this case, the list of malicious transactions will be forwarded to the cloud to identify

all a↵ected transactions by checking data received from all fog nodes. (This step will be

more e↵ective and e cient via cloud computing, since all data is now in one

highperformance machine that saves time by reducing unnecessary communication

between the fog nodes.) After the cloud receives those lists, it will scan the flushed logs

to identify any a↵ected transaction that is dependent on any of the damaged transactions

from the list.

Once the cloud finishes the damage assessment procedure and identifies all a↵ected

transactions, it will create a list of a↵ected transactions A↵ Lcloud,j for each fog node in the

system which has a↵ected transaction in its flushed data. The A↵ Lcloud,j lists will be sent

to their corresponding fog nodes to be used as input for our proposed algorithms to do

further detection. The cloud will identify all a↵ected transactions read by the FDR, since

the FDR log file is flushed to the cloud along with the data.

• If Ti is still in the local DB of Fog1, then the second procedure will be performed, as

outlined below, to detect any additional a↵ected transactions.

3.4.1.2 Second procedure:

Three algorithms will be launched once the fog receives the list of malicious

transactions MT L, detected by the IDS, or A↵ L cloud,j that is sent from the cloud. The first

algorithm, Algorithm 3.1, allows FM fog nodes to further detect all damaged transactions and

mark them as a↵ected. This algorithm will also confirm whether the main fog node

(FDR) has read any of these identified transactions. If so, the algorithm will send a list A↵ Lfdrj

to the FDR to use as input for further detection. The other two algorithms, Algorithms 3.2 and

3.3, are for the main fog node FDR. The Algorithm 3.2 could run simultaneously with Algorithm

3.1 once MT L, A↵ Lfdrcloud ,or A↵ Lfdrcloud,j list is received, to ensure fast detection of all a↵ected

transactions. The FDR fog node will not launch Algorithm 3.3 until any list of a↵ected

transactions from the FM fog nodes is received.

To illustrate the first model, suppose the IDS system detects Ti, Alice’s body tem-

perature, as a malicious transaction that is collected by the end user Sj1. Sj1 is connected

Algorithm 3.1 FM Fog Nodes Assessment Algorithm

Input:

• List of detected malicious transactions MT L done by IDS, or A↵ Lcloud,j list from the

cloud.

• The local FM log file.

Output:

• List of all a↵ected transactions A↵ Lfmj that will be detected by our proposed

algorithm in the Fog node FMj.

• A↵ Lfdrj List of all a↵ected transactions that have been read by FDR.

The Algorithm:

1: Creates a new a↵ected-transactions list A↵ Lfmj and initializes to null where j is the current

fog node ID.

2: Creates a new a↵ected list A↵ Lfdrj and initializes to null.

3: Takes MT L / A↵ Lcloud,j as input

4: Copies all malicious / a↵ected transactions Ti that exist in FMj from MT L / A↵ Lcloud,j list to

A↵ Lfmj list

5: if A↵ Lfmj =6 ; then

6: Scan the local log and

7: for every Tk 2 FMj that is dependent on any Ti 2 A↵ Lfmj do

8: Mark TK as a↵ected transaction

9: Add TK to the A↵ Lfmj list

10: end for

11: for every Ti 2 A↵ Lfmj do

12: Check if Ti has been read by FDR

13: Add Ti to the A↵ Lfdrj list

14: end for

15: end if

16: Send A↵ Lfdrj to FDR to do further detection 17:

Send A↵ Lfmj for data recovery.

Algorithm 3.2 FDR Fog Node Assessment Algorithm ”1”

Input:

• List of detected malicious transactions MT L, A↵ Lfdrcloud,j, or A↵ Lfdrcloud.

• The local FDR log file.

Output:

• List of all a↵ected transactions A↵ Lfdr.

The Algorithm:

1: Creates a new a↵ected-transactions list A↵ Lfdr and initializes to null

2: Takes MT L / A↵ Lfdrcloud,j / A↵ Lfdrcloud as input

3: Copies all malicious / a↵ected transactions Ti that exist in FDR from the input list to A↵ Lfdr

list

4: if A↵ Lfdr =6 ; then

5: Scan the local log and

6: for every Tk 2 FDR that is dependent on any Ti 2 A↵ Lfdr do

7: Mark TK as a↵ected transaction

8: Add TK to the A↵ Lfdr list

9: end for

10: end if

11: Send A↵ Lfdr for data recovery.

Algorithm 3.3 FDR Fog Node Assessment Algorithm ”2”

Input:

• A↵ Lfdrj list of a↵ected transactions received from other fog node FMj.

• The local FDR log file.

Output:

• List of all a↵ected transactions A↵ Lfdr.

The Algorithm:

1: for each a new a↵ected list that is received from FMj do

2: Creates a new a↵ected-transactions list A↵ Lfdr and initializes to null

3: Takes A↵ Lfdrj as input

4: if A↵ Lfdrj =6 ; then

5: Scan the local log and

6: for every Tk 2 FDR that is dependent on any Ti 2 A↵ Lfdrj do

7: Mark TK as a↵ected transaction

8: Add TK to both list the A↵ Lfdr and A↵ Lfdrj

9: end for there is no a↵ected transaction has been read from FMj

10: end if

11: Send A↵ Lfdr for data recovery. 12: end

for

to the fog node (FMj). Now assume that FMj has performed some local operations on its data

before the detection, as a matter of general routine, including Ti, such as:

1. Aggregate all the patients’ body temperature readings over a certain time Tagg,j

2. Calculate Alice’s average body temperature Tavg,j over the last six hours.

If FDR reads Ti, Tagg,j, and Tavg,j from FMj, then any transaction Tj 2 FDR that is

dependent on Ti , Tagg,j , or Tavg,j will be a↵ected. Note that there is no way FDR can know that

Tagg,j and Tavg,j are dependent on Ti, since they were calculated locally on the

FMj node. Therefore, any transactions that belong to FDR and are dependent on Tagg,j or Tavg,j

will not be detected by FDR itself until FDR gets a list of all a↵ected transactions from FMj.

Assume, for the following transactions T1j , T2j, and T3j 2 FDR, that:

• T1j is the doctor’s report, that is dependent on the malicious transaction Ti;

• T2j is dependent on Tagg,j to do any kind of study or to make a budget of the hospital;

• T3j, the prescription given to Alice, is dependent on Tavg,j and has some side e↵ects that

may a↵ect other data, such as heart rate or blood pressure.

Now suppose the IDS has already detected all malicious transactions including Ti and sent

them as list MT L to the system. Then the first procedure will check each malicious transaction

on MT L to determine whether it has been flushed to the cloud. Suppose, however, that Ti is

still on the local DB of FMj. In that case, the second procedure will pursue further

detection.

Thus, the FDR will run Algorithm 3.2 while all other a↵ected fog nodes FMj run

Algorithm 3.1 simultaneously. As Algorithm 3.1 runs, each a↵ected FM fog node will create two

lists:

• A↵ Lfmj will get a copy of all malicious transactions that exist in FMj from MT L list. All

detected damage transactions in FMj will be added to this list.

• A↵ Lfdrj which will contain all a↵ected transactions read by FDR and detected by

Algorithm 3.1 in FMj.

In lines 6 - 10, the algorithm will go through every transaction in the log of FMj to

confirm whether any of them are dependent on malicious or a↵ected transactions from the list

A↵ Lfmj. If so, these transactions will also be marked as a↵ected and added to A↵ Lfmj. Thus,

Tagg,j and Tavg,j will be added to A↵ Lfmj, since they are both dependent on the malicious

transaction Ti.

In lines 11 - 14, this loop of algorithm is to check only the final A↵ Lfmj list of all

malicious and a↵ected transactions and confirm whether any have been read by FDR. If so,

these will be added to A↵ Lfdrj. Therefore, Ti , Tagg,j, and Tavg,j will be added to A↵ Lfdrj, since

they have been read by FDR. A↵ Lfdrj will then be sent to FDR to use as input for Algorithm 3.3

to do further detection, while A↵ Lfmj will be sent for data recovery.

Once Algorithm 3.3 receives A↵ Lfdrj, it will create a new a↵ected list, A↵ Lfdr. The

algorithm will go through all transactions in the FDR log to determine whether any depend on

the malicious or a↵ected transactions from A↵ Lfdrj. If so, these will be marked as a↵ected

transactions and added to both A↵ Lfdr and A↵ Lfdrj. T1j, T2j, and T3j will thus be detected by

the end of this loop, and all three will be added to both lists. Then

A↵ Lfdr will be sent for data recovery.

3.5 The Second Proposed Architecture: Fog Nodes with Heterogeneous Data

In this model, we assume that all fog nodes have the same capability as well as the

ability to perform basic operations on data. However, in the “fog nodes with heterogeneous

data” model, there is no main fog node; each hospital department will have its own fog node.

Thus, when a patient is moved from one department to another, his or her data will also be

moved to the fog node of that department, as shown in Fig. 3.2. The healthcare providers in

each department will have only access to patient data through their own fog node and will

write records or reports based on this information. All patients’ data will be collected using

end users and IoT devices, such as sensors, and will be sent to the local fog node FM in the

same department.

This model can be applied outside of hospitals as well, since patient data in smart cities

will likewise move from one fog node to another while patients are traveling. Write operations

can also be accessed from all nodes. Thus, unlike the “fog nodes with homogeneous data”

model, malicious transactions in the “fog nodes with heterogeneous data” model could spread

quickly and cause severe data damage. In order to resolve this issue, the fog nodes need to

cooperate with each other.

3.5.1 Damage Assessment Algorithm for the Second Model.

3.5.1.1 First procedure:

As in the first model, when malicious transactions are detected by the IDS, the affected

fog node will scan for the presence of that transaction in its local DB. If the transaction is not

there, that means it has been flushed to the cloud. The full procedure in such a case

Figure 3.2: Second proposed architecture “fog nodes with heterogeneous data”

is similar to that explained in section 3.4.1.1.

3.5.1.2 Second procedure:

Our proposed Algorithm 3.4 will be performed in case one of following list is received:

• The list of malicious transactions MT L.

• The list of a↵ected transactions from another Fog node A↵ Lfmxj.

• The list of a↵ected transactions that has been detected by cloud in the flushed data

A↵ Lcloud,j that might damage another transaction still residing in the local DB.

To illustrate the proposed algorithm for the second model, consider the following

example: Suppose that Bob has just arrived at the emergency room with a medical issue.

Algorithm 3.4 Damage Assessment Algorithm for the Second Model

Input:

• Malicious transactions list MT L, A↵ Lfmxj from another fog, or A↵ Lcloud,j.

• The local log file.

Output:

• List of all a↵ected transactions A↵ Lfmj.

• Sub-lists of a↵ected transactions for each FMx that has been read any damaged data

from FMj.

The Algorithm:

Once FMj receives any of the input list

1: Creates a new a↵ected list A↵ Lfmj and initializes to null where j is the current fog node ID.

2: Copy all malicious / a↵ected transactions Ti that exist in FMj from the received list to A↵

Lfmj list

3: Scan the local log and

4: for every Tk 2 FMj that is dependent on any Ti 2 A↵ Lfmj do

5: Mark TK as a↵ected transaction

6: Add TK to the A↵ Lfmj list

7: end for

8: for every Ti 2 A↵ Lfmj do

9: if Ti has been read by any other FMX then

10: Check If A↵ LfmjX list does not exist, Then

11: Creates a new a↵ected list A↵ LfmjX and initialize to null where x is the id of aimed Fog node

that reads the a↵ected transaction.

12: Add Ti to the A↵ Lfmjx list

13: end if

14: end for

15: Send A↵ LfmjX to proper FMx to do further detection 16: Send

A↵ Lfmj for data recovery.

All of Bob’s data will thus be sent to the Fog of the Emergency Room (FogER). A few hours later,

however, the doctors decided to move Bob to the Intensive Care Unit (ICU) because his heart

rate was not steady according to sensor S1 (call this transaction T1). Bob’s data will then also

be moved to the Fog for the Intensive Care Unit (FogICU). While Bob was in the ER, the

physicians performed their tests and wrote report (T2) and, based on that report, the nurses

gave Bob some antiarrhythmic medication (T3) to stabilize his heart rate.

Thus, transaction T2 is dependent on transaction T1, and T3 is dependent on T2. Suppose, also,

that medication T3 has some side e↵ects, such as abdominal pain (T4), hemoptysis (T5), or

hypoglycemia (T6). These three transactions should be taken into account.(This is an example

of why a↵ected and damaged transactions should not be deleted, but instead kept and marked

as a↵ected). Once Bob arrives in the ICU, he develops a reaction to the antiarrhythmic

medication T3. The critical care specialist, based on the data and reports T1, T2, and T3 from the

ER, decides to give Bob alternative antiarrhythmic medication TICU1.

Subsequently, the critical care specialist realizes that Bob has no heart issue and his

heart rate is normal. In the meantime, however, the IDS has notified the FogER that T1 is a

malicious transaction. There is then no way for FogICU to detect T2 and T3 as a↵ected

transactions, since they depend on T1 and they are done locally at FogER. Nevertheless, FogER

will be the only fog node in the entire system that can detect T2 and T3. Thus, when FogER

receives the malicious transaction list including T1, the model’s first procedure will confirm

whether T1 has been flushed to the cloud. Suppose that T1 is still in the local DB and has not

been flushed yet. FogER will then launch Algorithm 3.4, as described in the second procedure.

The first line of the algorithm will create the A↵ LFMER list to identify all a↵ected transactions

in the FogER. T1 will be copied to this list, since it still resides in the local DB. Next, lines 3 - 7

will scan the log file, starting from T1, and check each transaction sharing data dependency

with T1 or with any other transactions in the list. The algorithm will find T2 in this way, mark it

as an a↵ected transaction, and add it to A↵ LFMER. When the algorithm examines the next

transaction in the log for data dependency with any a↵ected transactions from A↵ LFMER, it

will now take T2 into consideration because T2 has just been added to the list. Thus, T3 will be

detected, marked as a↵ected, and added to A↵ LFMER.

After all transactions in the log file have been scanned and examined, lines 8 - 12 of

Algorithm 3.4 will confirm whether each a↵ected transaction has been read by another fog

node (to which it was moved when the patient was moved). If so, a sub-list of a↵ected

transactions will be created for each a↵ected fog node, and add to the list the a↵ected

transaction that has been read. In our example, transactions T1, T2, and T3 have been moved to

FogICU, so FogER will create a new sub-list A↵ LFMERICU and add T1, T2, and T3 to that sub-list.

Finally, A↵ LFMERICU will be sent to the FogICU for further detection, and the main a↵ected list

A↵ LFMER will be sent for data recovery. Once FogICU receives A↵ LFMERICU , it will use the list as

input in the same algorithm, and TICU1 will be detected as an a↵ected transaction, since there is

data dependency between TICU1 and the a↵ected transactions T1, T2, and T3. The process

continues until all a↵ected transactions are detected.

3.6 Experiments and Evaluation

3.6.1 Setup and Introduction

In the experiments, a personal computer with 16 gigabytes of RAM and a Dual-Core

Intel Core i7 processor with a speed of 3.1 GHz was used. The whole system environment was

simulated using Java to prove the model and algorithms’ applicability and e ciency. The quality

of the proposed algorithms was evaluated by performing experiments considering di↵erent

factors, including the number of transactions in each log file and the number of attacking

transactions and fog nodes in the system. The communication delay between fog nodes in the

experiments was ignored since we used a local personal computer.

For the first model, we implemented di↵erent factors in order to draw a comparison

between the two proposed models: the fog model using heterogeneous data, and the fog model

using homogeneous data. We calculated the total time required, from initial detection of

malicious transactions by the (IDS), to assess and detect all a↵ected transactions in the system.

Furthermore, we recommended the model most suitable, or proper, considering circumstance

and other factors, for use in the healthcare system or a similar environment .

For the second and third models we simulated two primary systems. The first system

represents distribution by private, trusted fog nodes. The second simulated system represents

distribution by public, non-trusted fog nodes. Then we applied our proposed damage

assessment and data recovery schemes, with minor modification, to both so that we might

study the di↵erences between them. Our goal is to show which model is more e cient, again

considering circumstance and other factors, for use with each scheme.

The factors we used for all models are as follow:

1. Number of transactions in each log files:

• 100 transactions

• 500 transactions

• 1000 transactions

2. Set of a↵ected transactions in the whole system:

• Less than 5 a↵ected transactions.

• 10 to 15 a↵ected transactions.

• 30 to 35 a↵ected transactions.

3. The number of fog nodes in each model

• 5 fog nodes.

• 10 fog nodes.

• 15 fog nodes.

• 20 fog nodes.

3.6.2 Simulation

We simulated the whole environment for each proposed model to prove the

applicability and e ciency of our models and algorithms. Then we evaluated the quality of the

proposed algorithms by experimenting with di↵erent factors such as number of transactions

in each log file, the number of a↵ected transactions in the whole system, and the number of fog

nodes in the system. We sought answers to the following:

• How e cient are the proposed damage assessments algorithms to detect all a↵ected

transactions and data items in the systems.

• Compute the total time for each proposed damage assessment algorithm once the

malicious transactions list has been received until all a↵ected transactions have been

identified. During this time the system will be unavailable so, we aim to minimize this

time as much as possible.

• How e cient are the proposed data recovery algorithms to return the damaged data

to consistent state.

• Compute time latency for each proposed data recovery algorithm from the a↵ected

transactions list has been received until the whole data items have been recovered.

During this time only the a↵ected transactions and data items will be unavailable to be

use so, we aim to minimize this time as much as possible.

Since our work is novel in the context of damage assessment in fog computing, there is no

existing work that we can compare the performance of the proposed systems against. For this

reason, the aim is to implement, test, and evaluate the proposed models and prove that they

are not only applicable but also accurate, scalable, and reasonable in the reported delays.

However, in some models , we compare the performance of the proposed sub-models against

each other to see which model is better for di↵erent circumstances.

3.6.3 Data-set

3.6.3.1 Log Files:

Since there is no available data-set for the log files of fog node computing, and this work

is novel, we generated random log files, vary in length, for every fog node in the system. The

contents of the log files may be di↵erent for each model based on given assumptions. For

example, in the first model the read operations and their values, as seen previously in the

section 3, will be added to the log files for that model. We performed our experiments based

on the three log file sizes described above, beginning with 100 transactions in each log file and

following through with 500, and finally 1000. The data dependency between the fog nodes was

inserted arbitrarily into the log files. Here is an example of the generated log files: [ r1(361,688)

r2(345,669) w4(372,607,689) r5(207,651) w1(227,688,688) w2(345,669,621) r3(399,653)

r4(282,634) w5(207,651,612) c1 c2 w3(399,653,635) r4(361,688) w5(374,678,643)

w3(279,657,640) c4 c5 c3 r6(238,689) w7(207,612,636) r8(356,641) r9(323,683)

w6(238,689,604) w7(262,679,633) w8(356,641,654) w9(323,683,635) w6(345,621,636) c7 c8

c9 w6(286,646,677) c6 w10(313,663,685) r10(351,604) c10 ] Below we explain the notations

used for read, write, and commit operations respectively.

• r2(345,669): is reading operation where rtransaction number (data item, value)

• w2(345,669,621): is writing operation where wtransaction number( data item, old value, new

value)

• c2 : The transaction 2 has been committed which means it is successfully completed.

3.6.3.2 Graphs

We used the adjacency list for directed graph representation due to its speed and space

e ciency technique [79]. In this situation, we represent the transaction T as vertex

V in the directed graphs. If there are |T| in the log files, then each list can have up to

|T| 1 transactions depend on the transaction dependency that we explained previously. Each

vertex in the adjacency list can be reached in constant time since we need only to refer to an

array.

Regarding the space complexity of the adjacency list, it is the best case scenario of graph

representation techniques for storing the directed graph in the computer. This technique will

save substantial space. Thus, the adjacency list will only take up to ⇥(V +E) space, where V is

the set of vertices which in our models is the number of transactions in the log file T, and E is

the set of edges which are the dependencies between two transactions [80]. Additionally, the

adjacency list allows us to easily insert a new edge or vertex without extra cost as we are using

a linked list structure and this representation is more informatic and provides easier tracking

of any adjacent nodes of node.

All local and global directed graphs were built simultaneously when the log files were

generated based on transaction-dependency relationships between the transactions, as

previously explained in Chapter 5. With each log file, two graphs were generated, one for the

model where there is no trusted fog node (no global graph) in the system and the other one

for the model where there is a trusted fog node in the system. The global graphs for the trusted

fog node were also generated for any transaction that accessed a data item from another fog

data service node in the system, as we elucidated in Chapter 5. The log files and graphs were

manually rechecked and examined as ground truth to ensure the correctness and accuracy of

the algorithms.

3.6.4 Evaluation First Model: Ensuring Data Integrity in Fog Computing Based

Healthcare Systems

In the healthcare systems model, we introduced two sub-models for fog computing

systems that manage healthcare data. The first one is an architecture using fog computing with

homogeneous data; the second one is an architecture using fog computing with heterogeneous

data. Then for each sub-model we proposed appropriate algorithms to determine the e↵ect of

an attack on the system and identify damaged data.

In this experiment our goal was to determine two important points. First, for each

model we needed to study the behavior of the damage assessment algorithm as it detected

a↵ected data items with varying factors designed for the experiment. Second, we performed

experiments to highlight the di↵erences between the two models. Which is the better

performing of the two and which factors influence that outcome?

As we mentioned in the simulation section, we generated di↵erent sets of log files. Each

set represented the number of fog nodes in the system with a di↵erent number of transactions

in the log file. So, in the experiment we began with a fixed number of fog nodes each time and

a di↵erent number of transactions in each log file. Each time a malicious transaction was

randomly inserted the results were classified into three di↵erent sets, of a↵ected transactions.

The first set is a set of less than five identified, a↵ected transactions. Ten to 15 identified,

a↵ected transactions made up the second set. The third set of identified, a↵ected transactions

numbers twenty to twenty-five. This transaction clustering is important in making a fair and

reasonable comparison of the proposed algorithms as they are impacted by other factors

including the number of fog nodes and the number of transactions in each log file. Each

transaction in each set was repeated approximately twenty times. Then the total time, from

insertion of the malicious transaction until all a↵ected data items in the system were identified,

was computed. The time required for each set to identify the damaged transactions was then

averaged. This average was calculated for use in investigating and evaluating our approach. We

compared the results, determining the factor or factors having a greater or lesser impact to the

algorithms.

• First Sub-Model “Fog Node Distribution with Homogeneous Data”

3.6.4.1 First Experiment: The impact of log file size on di↵erent number of fog nodes in

the homogeneous data model:

Figs. 3.3, 3.4, 3.5, and 3.6 explain the relationship between the number of transactions

in each log file, the number of a↵ected transactions, and the average time required by our

system to detect all a↵ected data items in the whole system. The average time was calculated

by averaging the detection time each set required to complete the tasks. The results show that

a log file of 100 transactions will take the system approximately 34 to 36 ms to detect all

a↵ected data items in the whole system no matter the number of a↵ected transactions. The

delay time in detecting all a↵ected data items in log files of 500 transactions increased by

approximately 21- 23 ms. The delay time for the system to identify all a↵ected transactions in

log files of 1000 transactions was only around 17 to 18 ms more than that, when compared to

500 transaction log files, and almost the double the time the system required to identify the

a↵ected transactions in log files of 100 transactions. So, the length of time the system remains

unavailable is considerably impacted by the number of transactions in the log files.

This applies regardless of the number of fog nodes or the number of a↵ected transactions in

each log file.

Figure 3.3: The impact of log file size on five fog nodes in the homogeneous data model.

35.3232

35.7348

36.4893

56.7130

58.3696

59.3570

75.0660

75.4021

77.1037

20.0000

30.0000

40.0000

50.0000

60.0000

70.0000

80.0000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

Figure 3.4: The impact of log file size on ten fog nodes in the homogeneous data model.

Figure 3.5: The impact of log file size on fifteen fog nodes in the homogeneous data model.

34.3429

35.5206

36.6769

57.9988

60.0527

59.9576

77.5699

78.5814

79.9547

20.0000

30.0000

40.0000

50.0000

60.0000

70.0000

80.0000

90.0000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

34.9200

36.1496

35.9506

56.8978

57.1518

58.5385

76.0736

76.7770

79.0392

20.0000

30.0000

40.0000

50.0000

60.0000

70.0000

80.0000

90.0000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

Figure 3.6: The impact of log file size on twenty fog nodes in the homogeneous data model.

3.6.4.2 Second Experiment:The impact of a variable number of fog nodes and sets of

a↵ected transactions on various size of log files in the homogeneous data

model:

This experiment was designed to evaluate the performance of our detection algorithm

in identifying all data items a↵ected by the introduction of a malicious transaction. Figs. 3.7,

3.8, and 3.9 summarize the relationship between the number of fog nodes and the sets of

a↵ected transactions. Again, each log file was fixed in sets of 100, 500, and 1000 transactions.

The goal of this experiment was to discover and study the impact of the di↵erent sets of

a↵ected transactions and the various number of fog nodes to our damage assessment

algorithm.

Figs. 3.7, 3.8, and 3.9 show that our algorithm performs essentially the same regardless

of log file size. The damage assessment algorithm detected all a↵ected data items with a

marginal change in time required to complete the task, either increasing or decreasing by less

32.7759

35.2110

36.6817

54.9039

57.9539

59.5581

73.5850

76.3439

78.2674

20.0000

30.0000

40.0000

50.0000

60.0000

70.0000

80.0000

90.0000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

than 0.5 ms, when the number of fog nodes increased. This held true regardless of log file size.

Furthermore, the number of a↵ected transactions in each set had only slight impact on delay

time: at roughly 0.5 to 1 ms.

Figs 3.7 through 3.9 further illustrate that the set of five a↵ected transactions entailed

less time than the other two sets for all variants of log file size and number of fog nodes.

Additionally, the set of ten to fifteen a↵ected transactions, for the most part, exacted less time

than the set of twenty to twenty-five. The little change that occurred here was due to the

algorithm computation.

In brief, these experiments have shown that the earlier IDS identifies malicious transactions,

the more e cient and faster damage assessment can be made and that the size of the log file

has the most impact on delay time.

Figure 3.7: The impact of a variable number of fog nodes and sets of a↵ected transactions on

log files of 100 T in the homogeneous data model.

32.0000

33.0000

34.0000

35.0000

36.0000

37.0000

Nodes

Number of Fog Nodes in the System

100

Less than 5

10-15

Figure 3.8: The impact of a variable number of fog nodes and sets of a↵ected transactions on

log files of 500 T in the homogeneous data model.

Figure 3.9: The impact of a variable number of fog nodes and sets of a↵ected transactions on

log files of 1000 T in the homogeneous data model.

• Second Sub-Model: “Fog Nodes Distribution with Heterogeneous Data”

52.0000

53.0000

54.0000

55.0000

56.0000

57.0000

58.0000

59.0000

60.0000

61.0000

Nodes

Number of Fog Nodes in the System

500

Less than 5

10-15

70.0000

72.0000

74.0000

76.0000

78.0000

80.0000

82.0000

Nodes

Number of Fog Nodes in the System

1000

Less than 5

10-15

3.6.4.3 Third Experiment: The impact of log file size on di↵erent number of fog nodes in

the heterogeneous data model:

This experiment uses the same variables as the experiment described in section 3.6.4.1.

We computed the average time the algorithm exacts to identify all a↵ected data items in the

whole system. The number of fog nodes was fixed to five, then to ten, fifteen, and twenty,

respectively. The numbers of transactions on each log file varied from 100 to 500, then to 1000.

The results were classified in di↵erent sets as indicated in Figs. 3.10, 3.11, 3.12, and 3.13. The

results show that a 100 transaction log file, results in a delay time around 36 to 42 ms for

detection of all a↵ected data items in the whole system for less than five a↵ected transactions.

And the delay time to detect the same set in a 500 transaction log file increased to 51 to 79 ms.

A 1000 transaction log file with fewer than five a↵ected transactions, rendered a delay time of

100 to 119 ms in identification of all a↵ected data items. This increase in delay time as it relates

to the number of transactions in the log file remains consistent regardless of the number of fog

nodes or a↵ected transactions in each log file. As the number of transactions in the log files has

a major e↵ect on delay time, system availability becomes further compromised as the

transaction count per log file increases.

Figure 3.10: The impact of log file size on five fog nodes in the Heterogeneous data model.

Figure 3.11: The impact of log file size on ten fog nodes in the Heterogeneous data model.

36.898

51.038

59.295

69.213

85.703

123.001

99.855

120.401

137.598

20.000

40.000

60.000

80.000

100.000

120.000

140.000

160.000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

37.605

57.853

70.205

79.072

91.118

129.904

109.727

123.277

152.102

20.000

40.000

60.000

80.000

100.000

120.000

140.000

160.000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

Figure 3.12: The impact of log file size on fifteen fog nodes in the Heterogeneous data model.

Figure 3.13: The impact of log file size on twenty fog nodes in the Heterogeneous data model.

3.6.4.4 Fourth Experiment: The impact of di↵erent sets of a↵ected transactions on

various number of fog nodes in the heterogeneous data model:

37.849

57.816

77.269

74.780

110.388

136.696

116.089

136.454

162.830

20.000

40.000

60.000

80.000

100.000

120.000

140.000

160.000

180.000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

43.057

49.125

74.891

73.290

104.162

159.632

119.154

155.513

179.227

20.000

40.000

60.000

80.000

100.000

120.000

140.000

160.000

180.000

200.000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

The second experiment was implemented to observe the impact of the di↵erent sets of

a↵ected transactions in the heterogeneous data model. Figs. 3.14, 3.15, 3.16, and 3.17

represent the results. The findings observed in this experiment are di↵erent than that of the

experiments in section 3.6.4.2 for the homogeneous data model. The results here show that a

log file of 100 transactions produces, a delay time in ms that jumped from the thirties for

detecting the set of less than five a↵ected transactions to the fifties for ten to fifteen a↵ected

transactions, and into the seventies for twenty to twenty-five a↵ected transactions. The delay

time to detect the a↵ected data items in a log file of 500 varied from the small set of a↵ected

transactions to the larger set, ranging from ms in the 70’s for the set of less than five a↵ected

transactions to ms in the 150’s for the set of 20 to 25. The 1000 transaction log files registered

a delay time around the 100’s to 170’s ms to identify all a↵ected data items . So, unlike the

homogeneous data model, in this model the number of a↵ected transactions in the system has

significant e↵ect on the total time the system remains unavailable.

Figure 3.14: The impact of di↵erent sets of a↵ected transactions on five fog nodes in the

heterogeneous data model.

36.898

69.213

99.855

51.038

85.703

120.401

59.295

123.001

137.598

20.000

40.000

60.000

80.000

100.000

120.000

140.000

160.000

100

500

1000

Number of Transactions on Each Fog Node

Fog Nodes

Less than 5

10 -15

20 -25

Figure 3.15: The impact of di↵erent sets of a↵ected transactions on ten fog nodes in the

heterogeneous data model

Figure 3.16: The impact of di↵erent sets of a↵ected transactions on fifteen fog nodes in the

heterogeneous data model.

37.605

79.072

109.727

57.853

91.118

123.277

70.205

129.904

152.102

20.000

40.000

60.000

80.000

100.000

120.000

140.000

160.000

100

500

1000

Number of Transactions on Each Fog Node

Fog Nodes

Less than 5

10 -15

20 -25

Figure 3.17: The impact of di↵erent sets of a↵ected transactions on twenty fog nodes in the

heterogeneous data model.

3.6.4.5 Fifth Experiment: The impact of a variable number of fog nodes and sets of

a↵ected transactions on various size of log files in the heterogeneous data

model:

Investigation was also conducted into the relationship between the number of fog

nodes and the di↵erent sets of a↵ected transactions. Figs. 3.18, 3.19, and 3.20 describe the

results. The number of transactions on each log file here was fixed to 100, then 500, and finally

to 1000. The objective was to study the impact of the di↵erent sets of a↵ected transactions

with a variable number of fog nodes while keeping a fixed number of transactions in the fog

file. As we see in these figures, the performance of the proposed algorithm generated roughly

the same outcome with all di↵erent log file sizes. We found that the time needed for our

damage assessment algorithm to detect all a↵ected data items increased by 1 - 10 ms, when

the number of fog nodes increased. This remained consistent regardless of log file size.

43.057

73.290

119.154

49.125

104.162

155.513

74.891

159.632

179.227

20.000

40.000

60.000

80.000

100.000

120.000

140.000

160.000

180.000

200.000

100

500

1000

Number of Transactions on Each Fog Node

Fog Nodes

Less than 5

10 -15

20 -25

Figure 3.18: The impact of a variable number of fog nodes and sets of a↵ected transactions on

log files of 100 T in the heterogeneous data model.

Figure 3.19: The impact of a variable number of fog nodes and sets of a↵ected transactions on

log files of 500 T in the heterogeneous data model.

0.0000

10.0000

20.0000

30.0000

40.0000

50.0000

60.0000

70.0000

80.0000

90.0000

Nodes

Number of Fog Nodes in the System

100

Less than 5

10-15

0.0000

20.0000

40.0000

60.0000

80.0000

100.0000

120.0000

140.0000

160.0000

180.0000

Nodes

Number of Fog Nodes in the System

500

Less than 5

10-15

Figure 3.20: The impact of a variable number of fog nodes and sets of a↵ected transactions on

log files of 1000 T in the heterogeneous data model.

3.6.4.6 Sixth Experiment: Fog Nodes Distribution with Homogeneous Data

Model versus Heterogeneous Data Model:

These experiments were executed to demonstrate the di↵erence between the two

proposed models and to discover, in consideration of all variables, which of the two is the

better performer. Figs. 3.21, 3.22, and 3.23 illustrate an overall comparison of the average total

time latency in milliseconds between these models . The result, supported by these figures,

indicates that the first model, the homogeneous model, performs better with all di↵erent sets

of a↵ected transactions.

However, with the smaller set of less than five a↵ected transactions and smaller log file

of 100 transactions, the di↵erence was slight; the first model exceeded the second by only 1 -

3 ms ( Fig. 3.21). With the same smaller set of less than five a↵ected transactions the di↵erence

between the two models was a more significant 10 to 20 ms when the number of transactions

0.0000

50.0000

100.0000

150.0000

200.0000

Nodes

Number of Fog Nodes in the System

1000

Less than 5

10-15

increased from 100 to 500. Increasing the size of log files to 1000 transactions again rendered

a significant di↵erence of 20 to 30 ms. Figs. 3.22 and 3.23 illustrate the clearly meaningful

di↵erence between the two models with the introduction of the two larger sets of a↵ected

transactions. Briefly, the first model required less time than the second model, by half in log

files of 500 transactions, and by a third in log files of 1000 transactions.

The explanation for that lies in the number of fog nodes that will be a↵ected by the

malicious transaction. With the small set of less than five a↵ected transactions, the damage

will usually only a↵ect an average of up to three fog nodes. In the worst case, the architecture

of the first model will prevent the damage of one malicious transaction from spreading to more

than two fog nodes .

But in the second model the larger set of a↵ected transactions could impact a greater

number of fog nodes. So each log file in each a↵ected fog node must be scanned in the second

model, while the first model need only scan two fog nodes at most, the initial a↵ected Fog

Monitor node and the FDR fog node if it read the damaged data items. This scanning

requirement is also the reason that causes the variations in delay time in the second model. As

shown in Fig. 3.23 there are noticeable di↵erences in average delay time from one group of fog

nodes to another in the second model with 1000 transactions. For example, if a malicious

transaction a↵ected fifteen transactions in the system, then all those a↵ected transactions

could be in one fog node or in five fog nodes or more.

In closing, the model with homogeneous data stabilizes the results and speeds the

detection process, minimizing the system’s unavailability. Although, the model with

heterogeneous data is needed as well because it is more appropriately applicable to most

situations.

Figure 3.21: Comparison between homogeneous data model and heterogeneous data model

on a set of less than five a↵ected transactions

Figure 3.22: Comparison between homogeneous data model and heterogeneous data model

on set of 10 to 15 a↵ected Transactions

10.000

30.000

50.000

70.000

90.000

110.000

130.000

100

500

1000

100

500

1000

100

500

1000

100

500

1000

Nodes

Less Than 5 Affected Transactions

Model 1

Model 2

10.000

30.000

50.000

70.000

90.000

110.000

130.000

150.000

100

500

1000

100

500

1000

100

500

1000

100

500

1000

Nodes

Affected Transactions

Model 1

Model 2

Figure 3.23: Comparison between homogeneous data model and heterogeneous data model

on a set of 20 -25 a↵ected Transactions

4 Ensuring Data Integrity in Fog Computing Based Critical Infrastructure

Systems Model

Some of the following paragraphs, figures, and algorithms that will be introduced in

this chapter have been already published in our work [48] as shown in the publications and

reprint permissions chapter 7.

4.1 Introduction

These days the Internet of Things (IoT) is prevalent and trending as evidenced by the

significant increase in wearable technology, smart homes and buildings, connected vehicles,

and smart grids. The estimated number of connected IoT and smart devices by 2025 is

expected to become 75 billion worldwide [1]. This will produce an enormous amount of data

10.000

30.000

50.000

70.000

90.000

110.000

130.000

150.000

170.000

100

500

1000

100

500

1000

100

500

1000

100

500

1000

Nodes

Affected Transactions

that are predicted to total more than 79 zettabytes [2]. Due to the limitation and restriction

of bandwidth, as well as the rapid growth in the amount of data produced, the current

architecture of internet systems will be inadequate to manage and move that volume of data

to the cloud. In many scenarios, this will be impossible to do, especially with the increasing

number of IoT devices in use. Furthermore, some sensitive and real-time applications play

integral roles in our lives, such as connected car technologies, video conference applications,

and health monitoring devices, all of which require low-latency and location awareness to

provide satisfying and high-quality services [4].

In addition, IoT devices such as smart meters in modern smart cities will not only

produce a massive amount of data but the heterogeneity of that data will need to be

processed

in real-time [23]. This data will not be valuable enough without exploiting the maximum

benefits from other technologies. It is unmanageable and nearly impossible for the cloud to

handle by itself so many kinds of tasks, such as processing the aggregate data, analyzing them,

and storing them [24]. For that reason, fog computing was presented by Cisco [6]. Fog

computing is a decentralized computing infrastructure that allows end users’ data to be

computed, stored, and promoted on other applications and network services that are located

between the data source and the cloud computing data centers.

Fog computing technology is trending these days because it has several characteristics

that can improve the e ciency of transporting data to the cloud. This is very significant in the

age of cloud processing because it complements cloud computing and allows analytics to

perform resource, intensive, and extended term analytics [10]. One of the essential

characteristics of fog computing is its location at the edge of networks, providing end users

with high-quality services and low latency. Many current devices and applications, such as

smart meters, networked games, and video streaming, require location awareness and low

latency to provide a higher quality of service and performance. Alternative fundamental

characteristics are the widely dispersed and significant numbers of fog nodes that will be

geographically available. This design supports mobility in many applications, including service

in moving vehicles. The utilization of fog computing will also contribute to the benefits of

conserving bandwidth and enhancing the privacy and security of sensitive data. Most of the

data will be processed locally at the fog node, meaning that the amount of data needing to be

sent to the cloud for processing will be diminished, thereby minimizing bandwidth

consumption and maximizing the privacy of transmitting sensitive data [8, 9].

In the potential for smart cities, fog computing will help the IoT and smart meter devices

process the data and make quick decisions to take the right action within a critical time-

frame and to aggregate only the indispensable data for the cloud. Services and utility

companies, such as water and electric companies, can exploit fog computing technology to

manage and analyze the volume of consumers’ data. There are many existing studies on how

to expand the e ciency of fog computing in smart cities and to solve technical issues related to

the large volume of data that needs fusion and integration to the cloud [22]. Moreover, while

security and privacy issues have been addressed by many researchers, other aspects need

more attention, such as a case in which a protection system fails during a cyberattack and

costumers’ data need to be recovered. This study aims to detect all transactions that are

a↵ected by any malicious transaction, recover the correct value of data, and ensure the

integrity of consumer data in a fog computing environment in smart cities.

4.2 The Model

In this section, a unique architecture for using a distributed fog node system in smart

cities to manage the consumer data of utility services will be proposed. Then, cooperative

algorithms will be pro↵ered for identifying, assessing, recovering, and restoring all the

damaged and a↵ected data created by an attack. The goal is the restoration of a reliable

database. In the proposed model, it is assumed that the Intrusion Detection System (IDS) is

responsible for detecting malicious transactions in the system and providing a list of those

transactions to the damage assessment algorithms. Each fog node in the proposed architecture

must have its own log file and use a strict serializable history. All operations in the log file need

to be in the same order in the history. The log files cannot be user modified at any time. Since

the log files will contain a record of every modification to the value of any data item that is

updated by write operations, all read operations are also required to be stored in the log files

to identify the data dependencies between the operations and the transactions and among the

detections of the victim fog nodes in the systems.

4.3 Model Nations

Table 5.1 shows a list of the notations and descriptions to be used in our proposed

approach.

Table 4.1: Notation used in our proposed approach description

Notation

Description

pub fog

The public fog nodes that are accessed by customers and utilities

providers.

usc fog

The private fog node for each utility service company.

MT L

The list of detected malicious transactions done by IDS.

DA Table

The damage audit table, which is a data structure that will be created

by the damage assessment algorithms to collect any data about

transactions that are needed to do the data recovery, such as the valid

and invalid read data items, data written, and the accessed fogs.

DI L

The damage item list that will contain all damaged data items that are

identified by our proposed damage assessment algorithms.

DIT Fogx

The Fogx damage item table, where x is the ID of the secondary a↵ected

fog node, which reads some of the damage data items from another fog

node.

VIT Fogx

The valid data items table that will be created by algorithms 3 or 4 to

add to it all recovered data items for the secondary a↵ected fog node

Fogx. It will be sent to Fogx to use it as input on algorithm 4.

wi(A,v1,v2)

The write operation of the transaction Ti; v1 is the before image, which

represents the old value of the data item A before the update. And v2 is

the after image, which is the new value of data item A after the update.

ri(A,v)

The read operation of transaction Ti where A is the data item and v is

the current value of A.

The transaction Ti has been committed which means it is successfully

completed and it will be recorded to the database.

The transaction Ti has been aborted and it will not a↵ect the database.

4.4 The Proposed Architecture

In the proposed model, each smart city will have several public fog nodes (pub fog),

which will be e ciently distributed to guarantee the quality of service at each point and in all

corners of the city. Private fog nodes will be included, with at least one private fog node for

utility service companies (usc fog), such as water, electricity, and gas utilities. The usc fog

nodes should be e↵ectively located in the center of the whole distributed system to ensure a

reliable connection to all pub fog nodes and provide di↵erent routes should one of the pub

fog nodes disconnect for any reason. Consumers will be able to send queries to pub fog nodes

only. Data may be retrieved from the local database if available there. Otherwise, the queries

will be forwarded to the appropriate usc fog node. Consumers are not allowed to directly

connect the usc fog nodes for security reasons. All queries related to those nodes will come

through the pub fog nodes. Customer utility usage data will be collected from smart homes and

buildings using IoT devices and smart meters. Usage data will be sent to the nearest e cient

pub fog nodes based on several factors, such as location and load balance.

It is assumed that each pub fog node in the system will have the ability to perform

some essential data operations, such as calculating customer average usage over a specific

time frame or aggregating the totals of selected data values. Those operations are fundamental

to optimization of the network bandwidth since the data sent over the network will be

diminished by aggregating the necessary data.

Additionally, as most customer data will be processed locally, at the edge of the

network, it will enhance privacy and security by reducing sensitive data transmittal. Each

Figure 4.1: The proposed architecture.

utility usc fog node receiving the data will also perform some essential computations, such as

calculating the daily bill and average daily customer usage. These computations by the utilities

are important in improving the quality of services in each city as the need for expansion of

services in peak seasons may become evident and shortages avoided. Utilities may use data to

plan fuel purchases or raise consumer awareness regarding consumption and conservation.

We assume that the city and all fog nodes in the system are in the same time zone and use the

same o cial local time.

4.5 The Proposed Damage Assessment Algorithms

4.5.1 Algorithm 1: The Main Damage Assessment Algorithm

The IDS is responsible for identifying the attacking transactions and sending a list of

them to the victim fog node. Whenever one or more malicious transactions are found on any

fog node in the system, the IDS will detect them and send them as a list (MT L) to that fog node

to be used as input in the proposed schemes. Once the fog node receives the list, it will launch

Algorithm 1, which is the main damage assessment algorithm.

As soon as Algorithm 1 is launched, it will create the damage audit table (DA Table)

and damage data item list (DI L). Both will be initialized to null. Then, the algorithm will scan

the local log file of the victim fog node, Fog1, beginning from the first attacking transaction of

(MT L) list, Ti. Ti will be added as a new record into DA Table since it is the first attacking

transaction. If the attacking transaction updates at least one data item, then this data item will

be damaged, and any other updating transactions that read this data will be a↵ected as well. It

important to collect and store all data items that have been updated and damaged by the

attacking transactions. Then, all transactions that have read those damaged data items can be

identified, and data dependency can be declared between the transactions and the fog nodes

in the entire system.

One of the main functionalities of this algorithm will be the collection of data before

damage occurs, and store those images, which represent the pre-attack value of the data item,

in the written data column on the DA Table. These images will be used later in the recovery

algorithm. Simultaneously, those damaged data items will be added to the damaged item list

to determine data dependency.

Also, the algorithm will examine every transaction in the log file following, the first

attack, to determine whether any other transaction is an attacking transaction, or a data access

transaction from another fog node, or an updating write transaction. In the case where the

transaction is an attacking transaction, the algorithm will perform as in the first attacking

transaction. However, if the transaction is an access transaction from another fog node (Fogx),

the algorithm will check every data item that has been read by Fogx. A new damage item table

for Fogx (DIT Fogx) will be created and all damaged data items that have been read by Fogx as

well as the transaction identification and timestamp of each data item, will be added to the DIT

Fogx.

Since a fog node may access the same data multiple times, it is essential to know the

transaction ID and time of access (timestamp); this will make it easy to find on its log file and

confirm that the damaged data items were not corrected later on in the fogx by valid updating.

In the meantime, the DA Table will be updated indicating that Fogx has read the damaged data

item, so when the recovery algorithm has successfully corrected the value of the damaged data

item, it will send the correct value to Fogx to use as input for its own recovery algorithm.

If the transaction is an updating transaction (Tw), and not an attacking transaction

belonging to the malicious transaction list, then it must be added to the DA Table and examined

to accomplish two goals. The first goal is to determine data dependency. All read operations

must be checked to confirm whether Tw has read any of the damaged data items that already

exist to the damaged item list. If so, those damaged data items will be added to the invalid read

column of Tw, and undamaged data items will be added to the valid read column. Then, all the

write operations will be checked to determine whether any have read

Algorithm 4.1 The Main Damage Assessment Algorithm

1: Create a new DA table and initialize to null

2: Create a new DI L and initialize to null

3: for every Ti the local log starting from the first attacking transactions of MT L do

4: if Ti is attacking transaction then

5: add it as a new record into DA Table every wi (A,v1,v2)

6: add (A,v1) pair to data written column

7: add A to the DI L if it is not there

9: else if Ti is transaction from another fog node x then every data item A read by Ti

10: if A 2 DI L then

11: if DIT Fogx does not exist then

12: Create a new DIT Fogx where x is the ID of aimed fog node that reads the a↵ected

transaction

13: Mark Ti as a↵ected transaction

14: Add Ti and A into DIT Fogx

15: Update the last column of DA Table

16: end if

17: end if

18:

19: else if Ti is updating transaction then

20: add it as a new record into DA Table every ri (A,v)

21: if A 2 DI L then

22: add A to invalid read column

23: add (A,v) to valid read column

24: end if

25:

26: for every wi (A,v1,v2) do

27: if invalid read column of Ti =6 ? then

28: add (A,v2) to data written column

29: add A to the DI L if it is not there check If (A 2 DI L)

30: add (A,v2) to data written column

31: delete A from DI L

32: end if

33: end for

34: if ci is found & (both invalid read and data written columns of Ti) = ? then

35: delete the record of Ti from DA Table

36: else if ai is found then

37: delete the record Ti from DA Table

38: end if

39: end if

40: end for

41: Send DIT Fogx to Fogx to do further detection

42: Send DA Table & DI L for data recovery (algorithm 3)

damaged data items. If so, that means the damage has spread and the written data item is also

corrupted. Therefore, it will be added to the damaged item list, if it is not already there.

However, if the transaction Tw updates any data item, (A), without reading any items from the

damaged item list, then the data item (A) will be further checked evaluate its inclusion in the

damaged item list. If (A) was updated without reading a corrupted transaction, that means it

is a valid write and the data item (A) has been refreshed, so (A) must be removed from the

damaged item list as in steps(28-30). The new value will be added to the data written column,

accomplishing the second goal of adding the non-attacking updating transaction to the DA

Table. Steps (31-34) will remove the unnecessary records from the damaged audit table in the

case where the Tw is aborted or both invalid read and data written columns of Tw are empty.

Finally, the damage item table DIT fogx will be sent to fogx to do further detection, while the

damage audit table and damage item list will be sent to Algorithm 3, which is the main data

recovery algorithm.

4.5.2 Algorithm 2: Secondary Fog Node Damage Assessment Algorithm

This algorithm is similar to the previous one, which is Algorithm 1, but there are some

di↵erences. The main di↵erence in the input of this algorithm is the damage item table (DIT

Fogx), which is one of the outputs of Algorithm 1. Let us say that fog1 is the main victim fog

node in the system, and it was attacked and maliciously updated in the transaction Ti, which

wrote the data item Z. Later on, the transaction Tj indicated that fogx has accessed fog1 and read

Z. Then, fogx updated some other data items, such as N and M, on its database based on data

item Z. Here we call fogx the secondary a↵ected fog node. Once the secondary a↵ected fog node

in our example (fogx) receives the damage item table (DIT fogx) that contains Z as a damaged

data item, its transaction ID (Tj), and its timestamp say 9:00:00 AM, it will create a new damage

audit table and initialize it to null. Note that this algorithm will use the received damage item

table (DIT fogx) to store and track the damage data items instead of creating a new damage

item list. The list data structure will not be supportive here since the exact time and transaction

ID of the damage data items must be known.

The algorithm will scan the log file and start from the first a↵ected transaction from the

received table. Therefore, whenever an a↵ected transaction that belongs to DIT fogx is found,

the steps (3-12) will insert it as new record to the damage audit table and check each read

operations if its belong to DIT fogx then add it to the invalid read column; otherwise, it will be

added to the valid read column. Moreover, for the write operations, the updated data items

along with its new values will be added to the data written column as well as they will be added

to the DIT fogx table if they are not there. In our example, data items N and M will be added to

the DIT fogx and the data written column in DA Table. The rest of the algorithm is the same as

Algorithm 1 except when any data damage is found, the time of its occurrence must be taken

into account. Therefore, if fogx reads the data items M and N at any time before 9:00:00 AM and

then updates some other data item value, those updating transactions will not be a↵ected. In

a like manner, the damage item table, if there is one, will be sent to fogy while the damage audit

table and damage item list will be sent to Algorithm 4, which is data recovery algorithm for the

secondary fog node. The process continues until all the a↵ected transactions in the entire

system are detected.

Algorithm 4.2 Secondary Fog Node Damage Assessment

Once Fogx receives the DIT Fogx

1: Create a new DA table and initialize to null

2: for every Ti in the local log starting from the first a↵ected transaction on DIT Fogx do

3: if Ti 2 DIT Fogx && mark as a↵ected then

4: add a record for Ti into DA Table

5: for every ri (A,v) do

6: if A 2 DIT Fogx then

7: add A to invalid read column

8: add (A,v) to valid read column

9: end if

10: end for

11: for every wi (A,v1,v2) do

12: add (A,v2) pair to data written column

13: add A into DIT Fogx if it is not there

14: end for

15: else if Ti is transaction from another fog node y then

16: for every data item A read by Ti do

17: if A 2 DIT Fogx & Ti Timestamp Timestamp of damaged data item transaction then

18: if DIT Fogy does not exist then

19: Create a new DIT Fogy where y is the ID of aimed fog node that reads the a↵ected

transaction

20: Mark Ti as a↵ected transaction

21: Add Ti and A into DIT Fogy

22: Update the last column of DA Table

23: end if

24: end if

25: end for

26: else if Ti is updating transaction then

27: add it as a new record into DA Table

28: for every ri (A,v) do

29: if A 2 DIT Fogx & Ti Timestamp Timestamp of damaged data item transaction then

30: add A to invalid read column

31: add (A,v) to valid read column

32: end if

33: end for

34: for every wi (A,v1,v2) do

35: if invalid read column of Ti =6 ? then

36: add (A,v2) to data written column

37: add a record of Ti into DIT Fogx with data item A if it is not there check If (A 2 DIT Fogx)

38: add (A,v2) to data written column

39: delete A from DIT Fogx

40: end if

41: end for

42: if ci is found & (both invalid read and data written columns of Ti) = ? then

43: delete the record of Ti from DA Table

44: else if ai is found then

45: delete the record Ti from DA Table

46: end if

47: end if

48: end for

49: Send DIT Fogy to Fogy to do further detection

50: Send DA Table & DIT Fogx for recovery (algorithm 4)

4.6 The Proposed Data Recovery Algorithms

4.6.1 Algorithm 3: The Main Data Recovery Algorithm

Immediately after Algorithm 1 has accomplished its task and sent the damage audit

table (DA Table) and damage item list (DI L) to the main data recovery algorithm, which is

Algorithm 3, all the data items in the main victim fog node will be available to be used except

the damaged data items. Therefore, the availability of the system will be increased. Once

Algorithm 3 receives the damage audit table, it will scan only the records of the DA Table that

reads invalid data items. Whenever a record of the data items in the invalid read column is

found, the algorithm will perform three important steps. In the first step, it will take each data

item A in the invalid read column and scan the data written column upward, beginning from

the former record of DA Table, to find the last updated value of A, which must have the correct

value. Then, this value will be added as a pair (A, v) to the valid read column, and data item A

will be deleted from the invalid read column and so on until all the data items in the invalid

read column in the same record have been recovered. The second step is to recompute each

data item in the data written column in the same record by reading the new values from the

valid read column. Certainly, after those two steps are successfully completed, all the data

items in that record should have the correct values, as no attacking has occurred. The last step

is to check the last column in the same record, which is the column (fog ID), to find out if any

data item from that record has been read by another fog node in the system; if so, a new valid

data items table (VIT Fogx) will be created for each a↵ected fog node if it does not exist yet.

Then, the transaction ID along with the correct new values of each accessed data item will be

added to VIT Fogx. As soon as all the records in the damage audit table have been examined

and all three steps are checked, the VIT Fogx table will be sent to the corresponding fog node

Fogx. Finally, in steps 14-18, the new log that has just been generated while the data recovery

algorithm is in process will be checked to make sure all the data items have correct and valid

values.

4.6.2 Algorithm 4: Secondary Fog Node Data Recovery Algorithm

This algorithm is also similar to the main data recovery algorithm, Algorithm 3,

excluding two main di↵erences. The first is the input of Algorithm 4 will be three tables two of

them come from Algorithm 2 for the same fog node which they are the damage audit table DA

Table and the damage item table (DIT Fogx). And the third table input is the new valid data

items table (VIT Fogx) which comes from the data recovery algorithm of another fog node.

Secondly, this algorithm will check every record on the received damaged audit table. When

an a↵ected transaction is found, then every data item A in the invalid column will be deleted

after copying the (A, v) pair from the corresponding transaction on the VIT Fogx table to the

valid data column on DA Table. After all the damaged data items have been Algorithm 4.3 The

Main Recovery Algorithm

1: for each record in the DA Table do

2: if invalid read column of Ti =6 ? then

3: for every data item A in invalid read column do

4: find the last updated (A,v) pair in data written column of DA Table from the former records

5: add (A,v) to valid read column

6: delete A from invalid read column

7: end for

8: for every A in data written column do

9: recalculate the value of A using values in the valid read column

10: end for

11: if any fogx is existing in fog ID column then

12: if VIT Fogx does not exist then

13: Create a new VIT Fogx where x is the ID of aimed fog node that reads the a↵ected

transaction

14: end if

15: Add Ti and the (A,v) pair which is the correct value of A into VIT Fogx

16: end if

17: end if

18: end for

19: Send VIT Fogx to Fogx node

20: for every A in DI L do

21: check the new log that has just been created while the recovery process was in progress

22: if A is not modified in the log then

23: scan data written column of DA Table upward to find last updated value of A

24: substitute the value of A in the database with v

25: end if

26: end for

deleted on each record of the DA Table, the data written column will be checked to discern if

it is empty or not. If not, then the value v of each data item A in the data written column needs

to be recalculated by using the new values in the valid read column. However, the same

procedure used in Algorithm 3 will be employed if the record has a transaction with some data

items on the invalid read column. The process continues until all the a↵ected data items in the

entire system are recovered to a consistent state.

Algorithm 4.4 Secondary Fog Node Recovery Algorithm

Once Fogx receives the VIT Fogx

1: for each record in the DA Table do

2: if Ti is a↵ected transaction then

3: for every data item A in invalid read column do

4: copy the (A,v) pair from corresponding transaction on the VIT Fogx to the valid data

column on DA Table

5: delete A from invalid read column

6: end for

7: if the data written column =6 ? then

8: for every A in data written column do

9: recalculate the value of A using values in the valid read column

10: end for

11: end if

12: else if Ti is updating transaction & invalid read column =6 ? then

13: for every A in invalid read column do

14: find the last updated (A,v) pair in data written column of DA Table from the former records

15: add (A,v) to valid read column

16: delete A from invalid read column

17: end for

18: for every A in data written column do

19: recalculate the value of A using values in the valid read column

20: end for

21: if any fogy is existing in fog ID column then

22: if VIT Fogy does not exist then

23: Create a new VIT Fogy where y is the ID of aimed fog node that reads the a↵ected

transaction

24: end if

25: Add Ti and the (A,v) pair which is the correct value of A into VIT Fogy

26: end if

27:

28: Send VIT Fogy to Fogy node

29: for every A in DIT Fogx do

30: check the new log that has just been created while the recovery process was in progress

31: if A is not modified in the log then

32: scan data written column of DA Table upward to find last updated value of A

33: substitute the value of A in the database with v

34: end if

35: end for

4.7 An Example

To clarify the proposed scheme, let us consider the following example. Let us have in

our smart city three fog nodes. Fog1 and Fog2 are public fog nodes to collect consumer data

using smart meters. Fogx is a private fog node for the utility company to manage aggregated

data and calculate some important things, such as the bills and the amount of consumption.

Consider the following log schedules for each one of them:

SFog.1= r1(A, 5) r1(B, 4) w1(C, 11, 9) w1(G, 3, 9) r2(B, 4)c1 r2(G, 9) w2(A, 5, 13) w2(D, 0, 13)c2

fog2.r3(G, 9)c3 w4(A, 13, 5) w4(G, 2, 3)c4 r5(D, 13) r5(A, 5) r5(C, 9) w5(D, 2, 27)c5 r6(B, 4) w6(B, 4, 4)

r6(D, 16) w6(D, 16, 20) r6(A, 5) w6(A, 5, 25)c6 fog2.r7(D, 20)c7 r8(C, 9)c8 w9 (C, 9, 11)c9 r10(A, 25)

r10(C, 11) w10(E, 10, 36)c10 fog2.r11(E, 36)c11

SFog.2 = r9(K, 3) r9(fog1.T3.G, 9) w9(K, 3, 12) c9 r10(M, 10) r10(K, 12) w10(M, 10,

22)c10 fogx.r11(M, 22) c11 ... r14(fog1.T7.D, 20) r14(L, 4) w14(N, 17, 24) c14 r16(fog1.T11.E,

36) w16(P, 4 , 36)c16 fogx.r17 (P, 36) c17

SFog.x = r8(O, 6) w8(F, 6, 7)c8 r9(fog2.T11.M, 22) r9(H, 10) w9(I, 14, 32)c9 w10(J,

0, 18) c10 r11(fog2.T17.P, 36) r11(J, 18) w11(Q, 60, 54) c11 r12(Q, 54) r12(U, 12) w12(R, 57,

66)c12

Now, suppose the IDS detects the first transaction T1 on the Fog1 schedule as an

attacking transaction and data items (C) and (G) as being maliciously updated. Therefore, the

IDS will send the detected transaction T1 as the list (MT L) to Fog1. Once Fog1 receives the list,

it will launch Algorithm 1 since it is the main victim fog node in the system. Then, it will create

a new damage audit table (DA Table) and a new damage items list (DI L).

Consequently, the log file of Fog1 will be scanned, starting from the first attacking transaction

on the MT L, which is T1. Whenever an attacking transaction is found, such as T1 in our example,

it will be added to the DA Table as a new record. All the write operations of T1 will also be

checked, so whenever a data item is found, it will be added along with its old “before image”

value as a pair to the data written column, and the data items will be added to the damaged

items list if they are not already there. In our example, the pairs (C, 11),

(G, 3) are added to the data written column (see Table 4.2) while the data items (C) and (G)

will be added to DI L, and this will be the case for all attacking transactions that belong to (MT

L).

The algorithm will take the next transaction in the log file, which is T2. Since T2 is an

updating transaction, it will be added into the DA Table. Consequently, every reading

operation in T2 will be examined to ascertain if it reads any damaged data item from the

DI L; if so, the data item will be added to the invalid read column, as apparent with (G).

Otherwise, it will be added as a pair with its value to the valid read column as (B, 4) in our

example. The next transaction is T3, as we notice that Fog2 has read the data item

(G), which is a damaged data item. Steps 9-16 will examine that and mark it in the fog ID

column. Also, it will create a new damage item table for Fog2 (DIT Fog2) and add it to the table

with the transaction ID and the timestamp of the transaction when it has been committed (see

Table 4.3). Steps (28-30) of the algorithm will find that the damaged data items (A) and (G)

have been refreshed in T4 because they updated without reading any other damaged data

items. Therefore, they will be added along with their new values in the data that were written

and removed from the DI L. The process continues until the end of the log. Then, the DIT Fog2

will be sent to Fog2 to be used as input for Algorithm 2, while the DA Table and DI L will be sent

to Algorithm 3, which is the main recovery algorithm.

Once Fog2 receives the DIT Fog2, it will launch Algorithm 2 and use DIT Fog2 as input to

do further assessment and detection. Note that this table will add any damaged data items that

are detected in Fog2, as shown in Table 4.6. Thus, a new damage audit table DA Table will be

created and initialized to null. It will scan the local log of Fog2, starting from the first a↵ected

transaction on the DIT Fog2, which is T9 in our example. Therefore, T9 will be added to the new

DA Table and for every read operation, the data item will be examined to find out if it belongs

to the DA Table; if so, it will be added to the invalid read column. Otherwise, it will be added to

the valid read column along with its value. Therefore, the data item (fog1.T3.G) will be added

to the invalid read, while the pair (K, 3) will be added to the valid read column (see Table 4.4).

However, it will do the same thing for the write operations as in Algorithm 1, so the updated

data item (K) along with its value (K, 12) will be added to the data written column. Meanwhile,

the data item (K) will be added with its timestamp into the DIT Fog2, as can be seen in Table

4.6, since it becomes a↵ected by reading the damaged data item (Fog1.T3.G). For T10, the

updating occurs after reading the damaged data item (K), and the access time of T10 for that

data item (K) comes after the timestamp of the damage data item in the DIT Fog2, so the

scenario (the same as shown in T2 in Fog1) will be repeated, as shown in Table 4.4. Note that

examining the timestamp of reading the damage data item is important in Algorithm 2 since

Fog2 may read the same data item twice from Fog1, once before it became damaged and once

after that, so any item accessed before the damage must be valid. Also, the damaged data item

may be refreshed after it has been read by Fog2. Therefore, the only way to determine the status

is to compare the committed times. Consequently, the process continues until the end of the

log. By the end, there will be two tables, the DA Table for fog2, which will be sent to Algorithm

4 to conduct the data recovery, and the new damage item table for Fogx (DIT Fogx) (Table 4.5),

which will be sent to Fogx to be used as an input for Algorithm 2 to do further detection. Once

Fogx receives the DIT Fogx, the same process as we discussed previously will be continued until

the end of the log of Fogx (see Tables 4.7 and 4.8).

As soon as Fog1 has done the damage assessment algorithm (Algorithm 1) and sent the

DA Table and DI L to Algorithm 3 to do the data recovery, which will be launched immediately,

and taken the DA Table and DI L as inputs, it will scan the DA Table from the start and search

for any transactions that read invalid data items. For example, T2 reads invalid data item (G),

and then the algorithm will look for the last valid update value of (G), which must be the closest

transaction before the T2. Therefore, T1 has to have the latest updated correct value of (G),

which is (3). Therefore, the pair (G, 3) will be copied to the valid read column, and (G) will be

removed from the invalid read column. After that, T2 will be recalculated using the new values,

as apparent in Table 4.9. Note that in this example, only the addition operation will be used for

simplicity; therefore, we consider that for any transaction where a write operation is found

after read operations, all the values of the read operations will be added together. After that,

the T3 will be taken, so it will do the same process. Additionally, it will find that Fog2 has read

the damage data item (G). Hence, a new valid data item table for Fog2 (VIT Fog2) will be created

and added to the transaction ID, which is T3 and the correct value of (G), which is (G, 3) (see

Table 4.10), and so on until the end of the DA Table. After that, VIT Fog2 will be sent to Fog2 to

be used as an input in the Algorithm 4 to recover the data.

Once Fog2 receives the VIT Fog2, it will launch Algorithm 4 and use VIT Fog2 along with

it is own DA Table to do data recovery. Then, every record in the DA Table will be checked.

Since the first record (T9 in our example) must be an a↵ected transaction from Fog1, then VIT

Fog2 should have the correct and valid value of the damaged data item. Therefore, the new

value of data item (G) will be copied from VIT Fog2 to the valid read column of the DA Table

and remove it from invalid read. After that, T9 will be recalculated using the new values (as

shown in Table 4.11). The rest of the algorithm will be the same as Algorithm 3, and the same

thing will be done in Fogx after it receives the VIT Fogx from

Fog2 (see Tables 4.12 and 4.13).

Table 4.2: The Damage Audit Table for Fog1

T Id

Data written

Valid read

Invalid

Fog ID

(C, 11), (G, 3)

(A, 13), (D, 13)

(B, 4)

Fog2

(A, 5), (G, 3)

(D, 27)

(A, 5)

C, D

(D, 20), (A, 25)

(B, 4), (A, 5)

Fog2

(C, 11)

T10

(E, 36)

(C, 11)

T11

Fog2

Table 4.3: Fog2 Damage Item Table Created by Fog1

Transaction Id

Damaged Data Items

Timestamp

fog1.T3

9:00:00 AM

fog1.T7

9:00:30 AM

fog1.T11

9:01:00 AM

Table 4.4: The Damage Audit Table for fog2

T Id

Data written

Valid read

Invalid

Fog ID

(K, 12)

(K, 3)

fog1.T3.G

T10

(M, 22)

(M, 10)

T11

Fogx

T14

(N, 24)

(L, 4)

fog1.T7.D

T16

(P, 36)

fog1.T11.E

T17

Fogx

Table 4.5: Fogx Damage Item Table Created by Fog2

Transaction Id

Damaged Data Items

Timestamp

fog2.T11

9:00:20 AM

fog2.T17

9:01:05 AM

Table 4.6: DIT Fog2 with all damaged data items that are found on Fog2

Transaction Id

Damaged Data Items

Timestamp

fog1.T3

9:00:00 AM

fog1.T7

9:00:30 AM

fog1.T11

9:01:00 AM

9:00:00 AM

T10

9:00:17 AM

T14

9:00:30 AM

T16

9:01:00 AM

Table 4.7: The Damage Audit Table for fogx

T Id

Data Written

Valid Read

Invalid

fogID

(I,32)

(H,10)

fog2.T11.M

T11

(Q,54)

(J,18)

fog2.T17.P

T12

(R,66)

(U,12)

Table 4.8: DIT Fogx with all damaged data items that are found on Fogx

Transaction Id

Damaged Data Items

Timestamp

fog2.T11

9:00:20 AM

fog2.T17

9:01:05 AM

9:00:20 AM

T11

9:01:08 AM

T12

9:01:10 AM

Table 4.9: DA Table for fog1 after damaged data have been recovered

T Id

Data written

Valid read

Invalid

Fog ID

(C, 11), (G, 3)

(A, 7), (D, 7)

(B, 4), (G, 3)

(G, 3)

Fog2

(A, 5), (G, 3)

(D, 23)

(A,5), (C, 11), (D, 7)

(D, 27), (A, 32)

(B, 4), (A, 5), (D, 23)

(D, 27)

Fog2

(C, 11)

T10

(E, 43)

(C, 11), (A, 32)

T11

(E, 43)

Fog2

Table 4.10: VIT Fogx sent from fog1

Transaction Id

Valid Data Items

fog1.T3

(G,3)

fog1.T7

(D,27)

fog1.T11

(E,43)

Table 4.11: DA Table for fog2 after damaged data have been recovered

T Id

Data Written

Valid Read

Invalid

fogID

(K, 6)

(K,3), (fog1.T3.G, 3)

T10

(M, 16)

(M, 10), (K, 6)

T11

(M, 16)

Fogx

T14

(N, 31)

(L, 4), (fog1.T7.D, 27)

T16

(P, 43)

(fog1.T11.E, 43)

T17

(P, 43)

Fogx

Table 4.12: VIT Fogx sent from fog2

Transaction Id

Valid Data Items

fog2.T11

(M,16)

fog1.T17

(P,43)

Table 4.13: DA Table for fogx after damaged data have been recovered

T Id

Data Written

Valid Read

Invalid

fogID

(I, 26)

(H, 3), (fog2.T11.M, 16)

T11

(Q, 61)

(J, 18), (fog2.T17.P, 43)

T12

(R, 73)

(U, 12), (Q, 61)

4.8 Experiments and Evaluation

In section 3.6 in chapter 3, we explained the experimental setup, the simulation

environment, and datasets that have been used in detail.

4.8.1 Evaluation of the Second Model: Ensuring Integrity in Smart City Model

This model proposes the use of fog computing in smart cities to manage utility service

companies and consumer data. We also propose a novel technique to assess damage to data

caused by a malicious attack. The original data can then be recovered, and the database

returned to a consistent state as though no attack has occurred. This experiment aimed to

analyze the behavior of the proposed damage assessment algorithm as it detected a↵ected data

items with varying factors designed for the experiment. As declared in the simulation section,

di↵erent sets of log files were produced. Each set represented the number of fog nodes in the

system with a di↵erent number of transactions in the log files. In this experiment we started

with a fixed number of fog nodes each time and a di↵erent number of transactions in each log

file. Each time a malicious transaction was arbitrarily injected, the results were categorized

into di↵erent sets of a↵ected transactions: a set of 20 to 25 a↵ected transactions, a second set

of 10 to 15 identified, a↵ected transactions, and a third set of less than five identified, a↵ected

transactions. The clustering of the a↵ected transactions was necessary in evaluating the

proposed algorithms as they are impacted by other factors, such as the number of fog nodes

and the number of transactions in each log file.

Each transaction in each set was repeated approximately twenty times. Then the total

time, from insertion of the malicious transaction until all damage audit tables for all a↵ected

transactions were built, was computed. Then the average for each set to identify the damaged

data items was calculated. Also, the total time from receipt of the damage audit table for the

proposed data recovery algorithms to recover all a↵ected data items was computed. Then the

time required for each set for the recovery process was averaged. This average was calculated

for use in investigating and evaluating our approach. We compared the results, determining

the factor or factors having a greater or lesser impact to the algorithms.

4.8.1.1 First Experiment: The impact of log file size on di↵erent number of fog nodes

The relationship between the number of transactions in each log file, the number of

a↵ected transactions, and the average time required by our system to build all damage audit

tables for all a↵ected data items in the whole system were plotted on Figs. 4.2, 4.3, 4.4, and 4.5.

The average time was calculated by averaging the detection time each set required to complete

the tasks. The results show that a log file of 100 transactions will take the system

approximately 60 to 120 ms to detect all a↵ected data items in the whole system no matter the

number of a↵ected transactions. Also, the figures demonstrate that the delay time for the log

files of 100 transactions increased by 15 to 20 ms from the set of less than five a↵ected

transactions to the set of 10 to 15 a↵ected transactions. And the delay time the log files of

100 transactions increased by 20 to 40 ms from the set of 10 to 15 a↵ected transactions to the

set of 20 to 25 a↵ected transactions.

The time required to detect all a↵ected data items and create the audit tables for all

a↵ected transactions in the whole system with log files of 500 and 1000 transactions was

increased from the log files of 100 transactions for all di↵erent sets. Therefore, the time needed

for the system to identify all a↵ected data items in log files of 500 transactions was about 165

to 185 ms for the set of less than five a↵ected transactions. The time required for the same

processes increased by an average of 26 ms for the set of 10-15 a↵ected transactions and by

an average of 76 ms from the set of 10 -15 a↵ected transactions to the set of 20 to 25 a↵ected

transactions. Additionally, the delay time for the system to complete the damage assessment

algorithms in log files of 1000 transactions was roughly 190 ms for the set of less than five

a↵ected transactions. Then it increased by an average of 130 ms for the set of 10-15 a↵ected

transactions which was the greatest shifting in all results. Nonetheless, it increased a bit, by an

average of 26 ms, from the set of 10 -15 a↵ected transactions to the set of 20 to 25 a↵ected

transactions. This increase in delay time is related to the number of transactions in the log file,

the position of the malicious transaction in the log file, and the number of fog nodes infected.

For instance, Fig. 4.5 notes that the average delay time for the set of 10-15 a↵ected transactions

on 20 fog nodes with 500 log file transactions is considerably greater than its counterpart in

the other groups of fog nodes. Analysis of the results found that the malicious transactions

were randomly inserted in this particular set to the beginning of the log files, leading to many

more a↵ected fog nodes which, in turn, led to this delay. Therefore, it follows that the main

reasons for the delay results in the other experiments are determined by the variables

introduced: the number of a↵ected fog nodes, or the location of the malicious transactions in

the log file(s), or the number of a↵ected transactions. The latter of which will impact system

availability.

Figure 4.2: The impact of log file size on five fog nodes in the smart city model.

65.257

71.797

84.769

180.520

182.010

286.692

193.000

302.359

333.188

0.000

50.000

100.000

150.000

200.000

250.000

300.000

350.000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

Figure 4.3: The impact of log file size on ten fog nodes in the smart city model.

Figure 4.4: The impact of log file size on fifteen fog nodes in the smart city model.

57.882

87.876

105.673

186.289

208.491

288.122

192.445

319.896

338.811

0.000

50.000

100.000

150.000

200.000

250.000

300.000

350.000

400.000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

64.460

84.704

120.834

165.086

196.694

297.187

194.623

354.972

386.940

0.000

50.000

100.000

150.000

200.000

250.000

300.000

350.000

400.000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

Figure 4.5: The impact of log file size on twenty fog nodes in the smart city model.

4.8.1.2 Second Experiment: The impact of a variable number of fog nodes and sets of

a↵ected transactions on log files with di↵erent log files size

This experiment was designed to study the impact of a variable number of fog nodes on

our damage assessment algorithm. Hence, the relationship between the number of fog nodes

and the sets of a↵ected transactions have been illuminated in this experiment. The experiment

was conducted each time with log file sizes fixed to sets of 100 transactions, then to 500

transactions, then to 1000 transactions. Figs. 4.6, 4.7, and 4.8 illustrate steady performance by

the proposed damage assessment algorithms with the set of less than five a↵ected transactions

regardless of log file size.

However, the time the damage assessment algorithm needed to complete its tasks

increased when the number of fog nodes increased with the sets of 10 to 15 a↵ected

transactions and 20 to 25 a↵ected transactions. This held true regardless of log file size. The

increase in latency occurred here as the rising number of fog nodes on the system gave way to

61.855

76.828

116.261

185.443

253.116

289.794

190.942

323.356

363.181

0.000

50.000

100.000

150.000

200.000

250.000

300.000

350.000

400.000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

the chance of a greater number of infected fog nodes, especially with many a↵ected

transactions.

Figure 4.6: The impact of a variable number of fog nodes and sets of a↵ected transactions on

log files of 100 T in the smart city model.

Figure 4.7: The impact of a variable number of fog nodes and sets of a↵ected transactions on

log files of 500 T in the smart city model.

0.000

20.000

40.000

60.000

80.000

100.000

120.000

140.000

Nodes

Number of Fog Nodes in the System

100

Less than 5

10-15

0.000

50.000

100.000

150.000

200.000

250.000

300.000

350.000

Nodes

Number of Fog Nodes in the System

500

Less than 5

10-15

Figure 4.8: The impact of a variable number of fog nodes and sets of a↵ected transactions on

log files of 1000 T in the smart city model.

4.8.1.3 Third Experiment “The Evaluation of the Proposed Data Recovery Algorithms”

This experiment measures the performance of our proposed data recovery algorithms

in regaining all damaged data items and restoring their correct values as if no attack occurred.

For each a↵ected fog node, we calculated the time required, once the damage audit table and

damage item list has been received, for our proposed data recovery algorithms to recover and

render all the a↵ected data items to a consistent state. Then the average time for each set of

a↵ected transactions that we mentioned in Experiments 4.8.1 was computed. The following

Figs. 4.9, 4.10, 4.11, and 4.12. show the relationship between di↵erent numbers of transactions

on each log file and variable sets of a↵ected transactions with a fixed number of fog nodes.

Overall, we notice that the essential time to recover all damaged data items in the

whole system necessitates no more than 2.8 ms in all cases with all di↵erent numbers of fog

nodes, sets of a↵ected transactions, and sizes of log files. The set of less than five a↵ected

transactions needs approximately 1.1 to 1.5 ms to recover all data items regardless of the

0.000

100.000

200.000

300.000

400.000

500.000

Nodes

Number of Fog Nodes in the System

1000

Less than 5

10-15

number of fog nodes and the log file size; the other two sets took 0.09 to 0.96 ms more time.

Hence, during this time the a↵ected data items will be unavailable for use. It is impacted by the

number of a↵ected transactions in the system and holds true regardless of the number of fog

nodes or the number of transactions in each log file.

Figure 4.9: The impact of log file size on five fog nodes in the smart city model.

1.2867

1.6592

2.0357

1.2091

1.8250

1.9671

1.5476

2.0633

2.1624

0.0000

0.5000

1.0000

1.5000

2.0000

2.5000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

1.1713

1.6952

2.1167

1.2477

1.8010

2.3875

1.4852

1.9935

2.2915

0.0000

0.5000

1.0000

1.5000

2.0000

2.5000

3.0000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

Figure 4.10: The impact of log file size on ten fog nodes in the smart city model.

Figure 4.11: The impact of log file size on fifteen fog nodes in the smart city model.

Figure 4.12: The impact of log file size on twenty fog nodes in the smart city model.

5 Ensuring Data Integrity in Fog Nodes Distribution in Intelligent

Government Model

1.2986

1.7200

1.9389

1.1518

1.7665

2.1788

1.5275

1.9746

2.3876

0.0000

0.5000

1.0000

1.5000

2.0000

2.5000

3.0000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

1.4648

1.3244

1.8335

1.3823

1.7995

1.8989

1.3869

2.3689

2.7623

0.0000

0.5000

1.0000

1.5000

2.0000

2.5000

3.0000

LESS THAN 5

Number of Affected Transactions

Fog Nodes

100

500

1000

Some of the following paragraphs, figures, and algorithms that will be introduced in

this chapter have been already published in our work [64, 81] as shown in the publications

and reprint permissions chapter 7.

5.1 Introduction

In this era of technological evolution, many technologies, including the Internet of

Things (IoT), wearable devices, smart buildings, video gaming and streaming, and

smartphones, are an integral part of daily human life. Building stable and reliable

infrastructure for IoT systems necessitates consideration of rapid growth in the number of

connected IoT devices. It is estimated that these devices will number approximately 75 billion

by 2025 [1] and generate more than 79 zettabytes of data daily [2]. The present cloud and

internet architecture face significant challenges in handling and managing this massive

amount of data [5].

Another challenge present cloud and internet architecture faces is the provision of

adequate security and privacy measures for end users’ sensitive data. Government data is of

particular concern as attack on data within a government system may place a nation at risk

[25]. Sensitive applications such as tra c control systems, Real-Time Surveillance Camera

Monitoring, and Video-conference applications require real-time processing and location

awareness.

To overcome the limitations of cloud computing, fog computing, as a new platform, was

introduced by Cisco Systems in January, 2014. Fog computing is a virtualization architecture

in which vital computing resources are re-located close to the data source and the end-user.

Fog computing is able to process massive amounts of data, extend cloud storage, and o↵ers

rapid local responses [7]. Fog computing services make it a very satisfactory and practical

design solution for many sensitive applications that require real-time, location awareness,

including those systems on every level of government. Fog computing strengthens privacy and

security of data as data is stored and computed close to end-users at the edge of the network

[6, 9].

Governments around the world are creating intelligent environment systems that will

improve the quality of services they provide and the living conditions of their citizens. By

utilizing fog computing technology, they will be able to capture and utilize maximum benefit

of their systems and provide a safe environment with high-quality services. However, these

technologies do not come without risks. One of the most crucial issues in fog computing is

preserving the security and privacy of consumer data. While several researchers have

attempted to address security issues in intelligent government systems [82], there remain

some issues in need of more attention, including that of assessing damage to data that su↵er

malicious attacks.

Data damage assessment and recovery are fundamental to creating secure and reliable

databases. This is particularly true for a government data environment where the transmission

of time-critical sensitive data is commonplace. If one considers, for example, tra c control

systems, Real-Time Surveillance Camera Monitoring applications, as mentioned earlier, any

attack on these systems will paralyze their vital functions such as real-time processing and

location awareness features. When an attack on these critical databases violate integrity of

stored data the incident will result in serious consequences including damage to property and

even loss of life. Therefore, in addition to development of appropriate mechanisms for

adaptation of fog computing in intelligent systems, meeting security requirements to respond

to attacks by providing fast and accurate damage assessment and recovery techniques are

absolutely necessary.

Thus the primary objectives of this section are twofold: propose a novel model design

for an intelligent government system using fog computing technology to control and manage

the data across the entire system and propose a unique scheme to detect and assess data

a↵ected by malicious attacks in the model system.

5.2 Model

This section proposes using a unique distributed fog computing architecture to develop

an intelligent county government system for managing important data. It also presents a

cooperative technique for identifying and assessing damaged and a↵ected data following an

attack. In the proposed model, the Intrusion Detection System (IDS) is responsible for

detecting malicious transactions in the system and providing a copy of those transactions to

the damage-assessment algorithms. Each fog node in the proposed architecture must have its

own log file and is required to use a strict serializable history. The log files must be secured

such that they cannot be modified by unauthorized individuals.

5.3 Model Notation

A description of the notations to be used in our model can be found in Table 5.1.

Table 5.1: Notation used in our model

Notation

Description

sub-system

Distributed fog nodes sub-system representing each

authority/government agency.

pr fog

Primary fog data service node on the sub-system.

tsnt fog

Transient fog nodes responsible for collecting data by using

smart devices from end users across the county.

S{pr fogID.TM}

The set of detected malicious transactions in the system

detected by IDS.

G(Tn, E)

Graph Representation where Tn denotes the maximum

number of transactions in the node and E denotes the

number of edges

A↵-Lfogn

A↵ected-transactions list containing all a↵ected transactions

identified by proposed damage assessment algorithms.

wi(A,v1,v2)

The write operation of the transaction Ti; v1 is the before

image, which represents the value of the data item A before

updating. And v2 is the after image, which is the value of data

item A after it is updated.

ri(A,v)

The read operation of transaction Ti where A is the data item

and v is the current value of A.

The transaction Ti has been committed, which means it is

successfully completed and will be recorded to the database.

5.4 The Proposed Architecture

Generally, there are two main types of fog computing technology, public fog computing,

and private fog computing. Any distributed fog computing network to which access is limited

and restricted for use only by specific parties shall be a private fog computing network. A great

example of a private fog computing network is the campus fog computing distribution such as

school or college, and government fog computing distribution as what we will have here in this

chapter as an example [83].

In this proposed model, each government agency operates its own fog nodes

subsystem. Each sub-system has at least one primary fog-data-service node (pr fog) and

multiple transient-fog nodes (tsnt fog), which are well distributed to ensure quality of service

throughout the county. Some sub-systems may have restricted access to other sub-systems.

The tsnt fog are responsible for collecting data using IoT and smart devices, security

surveillance cameras, and kiosk stations from end-users across the county. Then the data is

transferred to the pr fog based on several factors, including location and selective data access

restrictions. Each pr fog in the system is able to perform some imperative operations such as

calculation and aggregation of required data. These operations are necessary to optimize the

bandwidth of networks since the data sent through it are aggregated by force. The aggregation

of essential data increases privacy and security because most of the data is now processed

locally at the edge of the network; local processing minimizes the transmission of sensitive

data over the network.

For example, the police department has one pr fog and several tsnt fogs that are

responsible for controlling and managing tra c lights, while other tsnt fogs are responsible for

collecting data from security cameras and so on. All data collected by tra c-light sensors and

surveillance cameras are transferred through tsnt fogs to the police-department pr fog.

Likewise, certain other pr fogs in the system, such as the fire department’s pr fog, have

restricted access to the data collected by tra c-lights sensors; the fire department’s access

allows emergency vehicles to change tra c lights and admission to the least congested routes.

As we stated early this model is a private distributed fog computing network so, It is

assumed that the whole system can be trusted because it is operated and surveilled by the

government. However, there is one trusted fog node in the system managing security matters

such as key management and distribution. It is located at the center of the system, ensuring a

reliable connection to all subsystems and providing a secondary pathway in the event a pr fog

is disconnected. The trusted fog node plays a leading role in damage assessment and data

recovery process (Fig. 5.5).

Figure 5.1: The Proposed Architecture.

5.5 The Proposed Damage Assessment Algorithms

This model implements a transaction-dependency graph to observe and monitor all

transactions in the entire system. Transaction-dependency graphs allow quick detection of all

transactions a↵ected by a malicious transaction. Transaction dependency is used instead of a

complicated data dependency where transaction updates are di cult to track and graphs are

sparser and more isolated. A transaction-dependency graph is easier to build and capable of

detecting and blocking malicious transactions significantly faster, thus preventing further

damage to data in the system. Una↵ected data items are available for immediate use. The

following subsections explain in detail each step of the proposed model.

5.5.1 Algorithm 5.1: Building Local Graphs

Each primary fog-data-service node pr fog builds a directed graph based on

transactiondependency relationships between transactions that have been successfully

committed to its database. The graph is produced and stored in a separate, unmodifiable file

with the original transactions in the same directory of the log file.

Each pr fog generates a graph by building a two-row matrix. The first row contains

associated data items and the second row contains the last transaction that updated each of

those data items (Tables 5.2 and 5.3). When a new transaction Ti is committed to the database,

the matrix is scanned to determine Ti’s precursors (parents). The new transaction is added as

a new vertex to the graph and the edges between Ti and its parents are inserted based on those

dependencies. Coincidentally, the matrix is updated with the newly committed transaction. So,

for each write operation for data item X in Ti, the algorithm will scan the matrix and update

the last transaction for data item X to Ti. However, if data item X does not exist in the matrix, it

will insert that data item and the transaction identification

Ti as a new record.

For example, consider the following log records for pr fogx and pr fogy:

pr fogx: r1(A, 45) r1(B, 34) w1(C, 29, 80) w1(G, 23, 18) r2(B, 34) c1 w2(A, 45, 48) w2(D, 12, 35) c2

r3(G, 18) c3 w4(A, 48, 69) w4(G, 18, 24) c4 r5(D, 35) r5(A, 69) w5(D, 35, 98 ) c5 r6(B, 34) w6(B, 34,

63) r6(D, 98) w6(D, 98, 24) r6(A, 69) w6(A, 69, 78) c6 r7(D, 24) c7 r8(C, 80)c8 r9(fogy.T6.V, 56) w9 (C,

80, 93) c9 r10(A, 78) r10(C, 93) w10(E, 39, 66)c10 r11(E, 66) c11.

Figure 5.2: Described Local Dependency Graphs for pr fogx.

Figure 5.3: Described Local Dependency Graphs for pr fogy.

pr fogy: r1(K, 58) r1(fogx.T4.G, 24)w1(K, 58, 98)c1 r2(M, 39) r2(K, 98)w2(M, 39, 59)c2 r3 (R, 43)c3

r4(fogx.T5.D, 35) r4(M, 59) w4(N, 36, 84) c4 r5(K, 98) w5(P, 43, 78)c5 w6(V, 56) c6

The log records for pr fogx indicate that T6 read data items B, D, and A. After T6 Algorithm

5.1 Building Local Graphs

1: Create a new Hash-table H and Initialize to null

2: Create a new Graph Representation G = (Tn, E) and Initialize to null

3: When Ti is committed in the local DB then

4: for each operation O 2 Ti do

5: if O is wi (A,v1,v2) then

6: add a pair (A, Ti ID) to H

7: add Ti as a new vertex to G if it does not exist

8: else if O is ri (A,v) then

9: if A 2 H then

10: add Ti as a new vertex to G if it does not exist

11: acquire the parents Tj ID from H

12: add edge from Tj to Ti

13: else if A 2 foreign fog node then

14: call global graph algorithm (Algorithm 5.2)

15: end if

16: else if O is ci then

17: end if

18: end for=0

is committed, it is added as a new vertex to the local graph of pr fogx, and the

directeddependency edge (the link) between T6 and other transactions on the graph is drawn

based on T6’s dependency relationships.

The algorithm locates the last updated transactions in the matrix for data items B, D,

and A (Table 5.2). The algorithm finds that T4 is the last transaction that updated data item A

and T5 last updated data item D. B does not exist in the matrix and so it has not been modified.

A directed edge is now drawn from T4 to T6 and from T5 to T6 (Figure 5.3). The matrix is

simultaneously updated. A new record for data item B is inserted and associated with T6 as the

last transaction to update B. In addition, the last updating transactions associated with data

items A and D are updated to T6 as shown on table 5.3.

Table 5.2: Matrix Tracking the Last Updated Transactions After T5 is committed

Data Items

Last updated T

Table 5.3: Matrix Tracking the Last Updated Transactions After T10 is committed

Data Items

Last updated T

T10

5.5.2 Algorithm 5.2: Building Global Graphs on the Trust Fog Node

As the trusted fog node plays an essential role in managing security and protection

considerations, including damage assessment and data recovery, the node obtains global

graphs for any transaction that accessed a data item in a pr fog node in the system.

Here is an example:

• Ti belonging to pr fogy accesses data item A. The last transaction updating data item A

was Tj on pr fogx.

• A copy of that last transaction’s graph updating data item A is sent to the global graph on

the trusted fog node and includes all preceding vertices that could a↵ect Tj directly or

indirectly.

• Transaction Ti is added to the global graph as a new child of Tj and an edge is drawn from

transaction x.Tj to y.Ti.

• Transaction Ti from pr fogy continues updating the global graph on the trusted fog node

by sending a copy of every subsequent transaction committed locally at pr fogy

(successor of Ti). This copy will be updated and sent frequently.

Figure 5.4: The Global Graph on The Trusted Node.

Figure 5.4, shows an example of the global graph generated using transaction activities

at the trusted fog node from pr fogx and pr fogy. As seen in the log records of pr fogy T1 read

data item G, which was updated by T4 in the log records of pr fogx. Then T4, pr fogx graph and

all its preceding elements are sent to the trusted fog node. This means any vertex that is a

precursor of T4 are now stored in the trusted fog node. In this case, T4 is the only

Algorithm 5.2 Building Global Graphs on the Trusted Fog Node

1: Create a new Global Graph Representation Gg = (Tn, E) on trusted fog node and

Initialize to null

2: (When Ti 2 fogx reads data item A 2 fogy) then

3: for each ri (A,v) 2 Ti do

4: acquire all predecessors of Tj from Gy

5: add Ti as a new vertex to Gg if it does not exist

6: add edge from fogy.Tj to fogx.Ti

7: end for

8: (When a new transaction Tz 2 pr fogx is committed where Tz is successor of Ti) then

Fog

9: add Tz as a new vertex to Gg if it does not exist 10: add

edge from Ti to Tz

vertex since it does not have parents. In addition, once T1 from pr fogy is committed, it is added

to both the global graph on the trusted fog node and the local pr fogy graph.

All new transactions added to the local graph of pr fogy and the successor of T1 are

added to the global graph. Thus:

• In the log records of pr fogy, T2 reads data item K from T1. T2 is added as a new vertex in

the local pr fogy graph.

• An edge is drawn from T1 to T2. The global graph is subsequently updated by adding T2.

• And so, it continues: T4 reads item M from T2 and T5 reads item K from T1. Hence,

T4 and T5 are added as new vertices to the local pr fogy graph. Edges are drawn from T2

to T4 and from T1 to T5. Then T4 and T5 are added to the global graph. The

pr fogy will continue sending updated copies of T1’s successor to the global graph upon

commit operating at its local database. This copy, as indicated, is updated and sent

frequently.

To prevent the global graph from becoming excessively large, a threshold is set based

on the system’s hardware capabilities. When the number of transactions in each fog node

reaches that threshold, the global graph is removed to the cloud for permanent storage.

5.5.3 Algorithm 5.3: Damage Assessment Algorithms

Once the IDS detects a malicious transaction in the system, it sends it to the trusted fog

node for identifying all transactions dependent on, and therefore a↵ected by, the malicious

transaction. Simultaneously, each victimized primary fog pr fog data service node in the

system receives the malicious transaction(s) detected on its database.

The pr fog can scan its own graphs and detect a↵ected transactions. This feature is

necessary as some local graphs containing transactions, malicious or not, have never been

accessed or read by another fog node. Those transactions have not been forwarded to the

trusted fog node. The pr fog scans only the graphs that it possesses using a modified Depth

First Search (MDFS) algorithm, beginning with the malicious transaction received from the

IDS.

Immediately following this part of the damage-assessment process, each subsystem

receives a list of all a↵ected transactions detected on its local database. All data items updated

by those transactions, hence considered damaged, are blocked from being accessed until

recovered. The rest of the data items are made available to users.

Algorithm 5.3 Damage Assessment Algorithm

1: Once S{pr fogID.TM} is received from IDS

2: Classify S{pr fogID.TM} to multi-set {S1{pr fog1.TM}..Sn{pr fogn.TM}}

3: Send each subset Sn{pr fogn.TM} to the (pr fogn) 4:

Send S{pr fogID.TM} to the trust fog node.

5: For the trust fog node and each other pr fogn that receive S or Sn.

6: MDFS (Gn , TM1 )

7: Create a new a↵ected-transactions list A↵-Lfogn and Initialize to null

8: Create a new Stack tranS and Initialize to null

9: add TM1 to tranS

10: mark TM1 as visited

11: while tranS is not empty do

12: TM1 = tranS.pop

13: add TM1 to A↵-Lfogn

14: for each child Ti of TM1 in Gn do

15: if Ti is not in then A↵-Lfogn

16: add Ti to tranS

17: mark Ti as visited and add it to A↵-Lfogn

18: end if

19: end for

20: end while

5.6 Applying the Transaction-Dependency Graph Scheme to public distributed fog

computing network

The implementation of the transaction-dependency graph scheme can also be applied

to the previous model architecture; the architecture for the use of a distributed fog node

system in smart cities to manage the consumer data of utility services. As we observed, this

model lacks the availability of a trusted fog node to build global graphs and handle security

matters such as damage assessment and data recovery. This model has only public fog nodes

distribution and belongs to more than one owner. No trusted fog node can exist in this kind

of distribution.

However, we can still modify our transaction-dependency graph scheme to enable

observation and monitoring of all transactions in the entire system of a model lacking a trusted

fog node. As we mentioned in section 4.2, Ensuring Integrity in Smart City Models, each fog

node in the proposed architecture must have its own log file and use a strict serializable history

and the graphs produced must be stored in a separate, unmodifiable file with the original

transactions in the same log file directory. These three assumptions remain compulsory for

building local graphs for each fog node.

5.6.1 Algorithm 5.4: Building Local Graphs for public distributed fog nodes

Each public fog node (pub fog) or private fog node for a utility service company (usc

fog) builds a directed graph based on transaction dependency relationships between

transactions that have been successfully committed to its database. However, When a new

transaction (Tx) is committed to the database, the algorithm will determine Tx’s dependency

(parents). Tx will then be inserted as a new vertex to the local graph, and the links between Tx

and its parents will be added on the basis of the dependencies. The fog node will update the

tracking mechanism in accordance with the recently committed transaction.

To illustrate the algorithm, we use the following example for the records of log for pr

fog1 and pub fog2 fog nodes:

pr fog1: r1(X, 32) w1(Z, 29, 80) w1(W, 89, 81) c1 r2(Z, 80) w2(X, 32, 22) w2(D,

12, 35) c2 r3(W, 81) r3(pub fog2.T2.F, 66) w3(W, 81, 91) c3 w4(X, 22, 77) c4r5(D, 35) r5(

X, 77) w5(D, 35, 98) c5r6(D, 98) w6(D, 98, 24) r6(X, 77) w6(X, 77, 78) c6 pub fog2: r1(E, 13) r1(pr

fog1.T1.W, 81) w1( E, 13, 39) c1 r2(F, 53) r2(E, 39) w2( F, 53, 66) c2 r3(R, 43) c3 r4(pr fog1.T5.D, 98)

r4(F, 66) w4(J, 79, 30) c4 r5(E, 39) w5(I, 43, 78) c5

The log record for pr fog1 indicates that T5 reads data items (D) and (X). Conse-

Figure 5.5: The Proposed Architecture.

quently, after T5 is committed, it will be added as a new vertex to the local graph of pr fog1, and

the directed dependency edge between T5 and other transactions on the graph will be added

on the basis of T5 dependency relationships. The algorithm will determine that the last

updated transaction for data item (X) is T4 and the last transaction that updates data item (D)

is T2. Hence, a directed edge will be drawn from T4 to T5 and from T2 to T5

(Figure 5.6 ).

However, when any transaction Ti reads a data item in one pub fog / pr fog node that

has been updated by Tj in another pub fog / pr fog node, then the transaction identification

(ID) of Ti will be added as a child of Tj on the local graph of the pub fog / pr fog node, in which

the item is initially updated. For example, in the log records of pub fog2, T1 reads Algorithm

5.4 Building Local Graphs for Public Distributed Fog Computing

1: Create a new Hash-table H and Initialize to null

2: Create a new Graph Representation G = (Tn, E) and Initialize to null

3: When Ti is committed in the local DB then

4: for each operation O 2 Ti do

5: if O is wi (A,v1,v2) then

6: add a pair (A, Ti ID) to H

7: add Ti as a new vertex to G if it does not exist

8: else if O is ri (A,v) && A 2 H then

9: add Ti as a new vertex to G if it does not exist

10: acquire the parents Tj ID from H

11: add edge from Tj to Ti

12: else if Tk 2 foreign fog node fogy reads data item A that updated by Ti then

13: add fogy.Tk as a new vertex to G if it does not exist

14: add edge from Ti to fogy.Tk

15: end if

16: end for

data item W that is updated by T1 in the log records of pr fog1. The transaction ID of T1 from

pub fog2 will then be added as a foreign child of T1 on the local graph of pr fog1. T4 from the log

of pub fog2 reads item D that is written by T5 on pr fog1, and the transaction ID of T4 from pub

fog2 will be added as a foreign child of T5 on the local graph of pr fog1.

Data item F is updated by T2 on pub fog2 and accessed by T3 from pr fog1. Accordingly,

T3 will be added as a foreign child of T2 on the local graph of pub fog2. The process continues

updating local graphs, given that transactions are successfully committed to the local database.

Figure 5.6 shows examples of the local graphs generated using transaction activities at pr fog1

and pub fog2.

Figure 5.6: Described Local Dependency Graphs for pr fog1 and pub fog2.

5.6.2 Algorithm 5.5: Damage Assessment Algorithms for Public Distributed Fog

Computing

Once the IDS detects a malicious transaction in the system, each fog node, pr fog or pub

fog is informed of the malicious transaction(s) detected on its database. The pr fog or pub fog

scrutinizes its own graphs and identifies a↵ected transactions. The compromised fog nodes

examine only the graphs that they possess using a modified Depth First Search algorithm

(MDFS), beginning with the first malicious transaction received from the IDS. All successors of

the malicious transaction will be considered a↵ected transactions and added to the a↵ected

list. However, if the transaction Ti from pub fog2 is found to be a successor of the initial

malicious transaction Tj on the pr fog1, then a sub-list of a↵ected transaction will be sent to pub

fog2 and used as input to the damage assessment algorithm. The process will continue until all

a↵ected transactions in the system have been identified.

pub

Soon after this phase of the damage assessment mechanism is accomplished each fog

Algorithm 5.5 Damage Assessment Algorithm for Public Distributed Fog Computing

1: Once S{fogID.TM} is received from IDS

2: Assort S{fogID.TM} to multi-set S1 ... Sn

3: Send Sx{fogx.TM} to the (fogx)

4: For each fogx that receive Sx

5: MDFS (Gn , TM1 )

6: Establish a new list for a↵ected transactions (A↵-Lfogx)

7: Establish a new Stack ST

8: add TM1 to ST

9: mark TM1 as visited

10: while ST is not empty do

11: TM1 = ST .pop

12: add TM1 to A↵-Lfogx

13: for each child Ti of TM1 in Gn do

14: if Ti 2/ A↵-Lfogx then

15: add Ti to ST

16: mark Ti as visited

17: add Ti to A↵-Lfogx

18: if Ti is foreign transaction 2 fogy then

19: add Ti to sub-list A↵-Lfogx,y

20: end if

21: end if

22: end for

23: end while

24: Send A↵-Lfogx,y to fogy to do further detection

node will have the final list of all a↵ected transactions detected on its local database. Any data

items updated by any of those a↵ected transactions will be blocked from access until recovered

as they are considered damaged data items. Una↵ected data items will remain available to

users.

5.7 Experiments and Evaluation

In section 3.6 in chapter 3, we explained the experimental setup, the simulation

environment, and datasets that have been used in detail.

5.7.1 Evaluation of the Third Model: Private Fog Nodes Distribution in Intelligent

Government County Model

In this experiment, we aimed to determine if the trusted fog node in the system which

is proposed to manage security matters such as key management and distribution, could play

a leading role in damage assessment. In this model we studied the behavior of the damage

assessment algorithm as it detected a↵ected transactions with di↵ering factors.

We started with a fixed number of fog nodes each time and a di↵erent number of

transactions in each log file. Each time we randomly inserted a malicious transaction and then

classified the results into three di↵erent clusters, or sets, of a↵ected transactions. The first set

comprises less than five identified, a↵ected transactions. The second set contains ten to fifteen

identified, a↵ected transactions, and the third set includes thirty to thirty-five identified,

a↵ected transactions. This clustering is important for making a fair and reasonable comparison

of the proposed algorithms as they are impacted by other factors such as the number of fog

nodes and the number of transactions in each log files. Each transaction in each set was

repeated approximately twenty times, and the total time from inserting the malicious

transaction until all a↵ected transactions were identified in the system was computed. Then

the average for each set was calculated for investigation and evaluation of our approach. Then

we compared the results to determine which factor(s) created a greater or lesser impact to the

algorithms.

5.7.1.1 First Experiment: The impact of the di↵erent sets of a↵ected transactions on

various fog nodes number

Figures 5.7, 5.8, 5.9, and 5.10 show the relationship between the number of a↵ected

transactions, the number of transactions on each log file, and the average time required by our

system to detect all a↵ected transactions in the whole system. The average time was calculated

by averaging the detection time each set of malicious transactions required. The result shows

that the number of a↵ected transactions that are detected has great e↵ect on the total time the

system remains unavailable. And this applies in all cases, regardless of the number of fog nodes

or the number of transactions on each log file.

Figure 5.7: The impact of the di↵erent sets of a↵ected transactions on five fog nodes

0.07684

0.07805

0.07829

0.12867

0.12805

0.12792

0.27592

0.27236

0.27592

0.00000

0.05000

0.10000

0.15000

0.20000

0.25000

0.30000

100

500

1000

Number of transactions on each fog node

Fog Nodes

Less than 5

10 -15

30 -35

Figure 5.8: The impact of the di↵erent sets of a↵ected transactions on ten fog nodes

Figure 5.9: The impact of the di↵erent sets of a↵ected transactions on fifteen fog nodes

0.07659

0.07864

0.07850

0.12840

0.12751

0.12795

0.26832

0.27282

0.27011

0.00000

0.05000

0.10000

0.15000

0.20000

0.25000

0.30000

100

500

1000

Number of Transactions on Each Fog Node

Fog Nodes

Less than 5

10 -15

30 -35

0.07691

0.08008

0.08075

0.12821

0.12814

0.12838

0.26651

0.27229

0.27129

0.00000

0.05000

0.10000

0.15000

0.20000

0.25000

0.30000

100

500

1000

Number of Transactions on Each Fog Node

Fog Nodes

Less than 5

10 -15

30 -35

Figure 5.10: The impact of the di↵erent set of a↵ected transactions on twenty fog nodes

5.7.1.2 Second Experiment: The impact of di↵erent number of transactions on various

number of fog nodes

Figures 5.11, 5.12, 5.13, and 5.14 show the relationship between the number of

transactions on each log file, and the average time required for our system to detect all a↵ected

transactions in the whole system. The result shows that the number of transactions does not

have a big impact on the total time the system will be unavailable. And this is the case with all

other scenarios, either with a di↵erent number of fog nodes in the system or a di↵erent set of

a↵ected transactions.

0.07920

0.07908

0.07995

0.12806

0.12719

0.12764

0.26373

0.26887

0.27269

0.00000

0.05000

0.10000

0.15000

0.20000

0.25000

0.30000

100

500

1000

Number of Transactions on Each Fog Node

Fog Nodes

Less than 5

10 -15

30 -35

Figure 5.11: The impact of di↵erent number of transactions on five fog nodes

Figure 5.12: The impact of di↵erent number of transactions on ten fog nodes

0.07684

0.12867

0.27592

0.07805

0.12805

0.27236

0.07829

0.12792

0.27592

0.00000

0.05000

0.10000

0.15000

0.20000

0.25000

0.30000

LESS THAN 5

Number of affected transactions

Fog Nodes

100

500

1000

Figure 5.13: The impact of di↵erent number of transactions on fifteen fog nodes

Figure 5.14: The impact of di↵erent number of transactions on twenty fog nodes

5.7.1.3 Third Experiment: The impact of a di↵erent number of transactions and fog

nodes on di↵erent sets of a↵ected transactions

0.07691

0.12821

0.26651

0.08008

0.12814

0.27229

0.08075

0.12838

0.27129

0.00000

0.05000

0.10000

0.15000

0.20000

0.25000

0.30000

LESS THAN 5

Number of affected transactions

fog nodes

100

500

1000

0.07920

0.12806

0.26373

0.07908

0.12719

0.26887

0.07995

0.12764

0.27269

0.00000

0.05000

0.10000

0.15000

0.20000

0.25000

0.30000

LESS THAN 5

Number of affected transactions

Fog Nodes

100

500

1000

This experiment represents the performance of our detection algorithm in identifying

all a↵ected transactions. The following Figures. 5.15, 5.16 and 5.17 show the relationship

between the number of transactions on each log file and the number of fog nodes. The sets of

a↵ected transactions that were used in this experiment were fixed at less than five, then ten to

fifteen, and finally to the set of thirty to thirty five.

Figure 5.15 indicates the set of a↵ected transactions was fixed at less than five and the

time needed for our damage assessment algorithm to detect all a↵ected transactions was

slightly increased when the number of fog nodes was increased. This scenario held true

regardless of log file size. The delay that occurred here was due to increasing size in the global

graph. The global graph size usually expands with a rise in transaction dependency, We

observed the global graph increasing in size with both the number of transactions on each log

file and the number of fog nodes. We also observed that the number of transactions in each log

file had little impact on the results. Hence, the log files containing 1000 and 500 transactions

took only slightly more time than those containing 100 transactions when we used the set of

less than five a↵ected transactions.

But when the set of a↵ected transactions was fixed at 10 to 15, the results di↵ered, as

seen in Fig. 5.16. Here we see that an increase in the number of fog nodes decreased the delay

time. With the larger set of a↵ected transactions, the global and local graph levels with small

log file size and fewer fog nodes show greater delay than the graphs with large log files and

more fog nodes.

The set of 30 to 35 a↵ected transactions produced di↵erent findings as shown on figure

5.17. A small log file of 100 transactions exhibited the same behavior as the previous set of 10

to 15 a↵ected transactions where the smaller number of fog nodes showed more time delay.

The delay decreased when the number of fog nodes increased. The log files containing 500

transactions were fairly stable for a bit before showing a decrease in delay with the increase

in fog nodes to 20, minimizing the number of transaction (node) levels on the graphs. Although,

for the 1000 transaction log file the time needed to detect all a↵ected transactions increased

slightly due to global and local graph growth.

To conclude, these experiments prove that the sooner IDS identifies the malicious

transactions the more e cient and faster damage assessment of the a↵ected transactions can

be made. The large spread of a↵ected transactions is the primary cause of delay in our

algorithms. This is due to the rise in the height and depth of the a↵ected sub-tree.

Figure 5.15: The impact of a di↵erent number of transactions and fog nodes on a set of less

than five a↵ected transactions

0.07400

0.07500

0.07600

0.07700

0.07800

0.07900

0.08000

0.08100

0.08200

Nodes

Less Than 5 Affected Transactions

100

500

1000

Figure 5.16: The impact of di↵erent number of transactions and fog nodes on set of ten to

fifteen a↵ected Transactions

Figure 5.17: The impact of a di↵erent number of transactions and fog nodes on a set of 30 -35

a↵ected Transactions

5.7.1.4 Fourth Experiment: Resource Requirement Cost

0.12600

0.12650

0.12700

0.12750

0.12800

0.12850

0.12900

Nodes

Affected Transactions

100

500

1000

0.25600

0.25800

0.26000

0.26200

0.26400

0.26600

0.26800

0.27000

0.27200

0.27400

0.27600

0.27800

Nodes

Affected Transactions

100

500

1000

Table 5.4 shows the space required to store the global graph file on the trusted fog node

and the local graph files on each pr fog. When the number of fog nodes in the system or the

number of transactions on each fog node increases, the size of the global graph file will

increase. At some point it will exceed the total size of all local graph files combined.

Nonetheless, the largest graph file size our experiment produced was approximately 390

Kilobytes, which is still very small, and will not cause any issue in terms of space requirements,

neither in the trusted fog node nor on pr fog nodes. Therefore this solution is not expensive in

terms of storage requirements since hardware storage today is massive, and all graphs in our

models, which represent real life situations, are sparse and will occupy an insignificant portion

of storage space. Even though, those graphs exceed the worst case space requirement scenario

for the adjacency list which is E = ⇥(V 2), when the graph is dense and there exists an edge

between all vertices v of the graph to all other vertices v, it will be the same space complexity

as the adjacency matrix. Keep in mind, this scenario is impossible and in conflict with our

submission regarding the log files since we assume the log must be serializable.

Table 5.4: Storage requirement in Bytes for graph files with existing of trusted fog node

Number

Fog

Nodes

Storage Requirement In Bytes

100 Transactions

500 Transactions

1000 Transactions

Global

Graph

Total Local

Log Files

Global

Graph

Total Local

Log Files

Global

Graph

Total Local

Log Files

3,857

29,535

38,423

177,345

90,978

370,110

7,351

65,200

79,425

400,750

182,027

842,220

12,403

96,600

121,354

603,750

283,796

1302,885

16,725

125,800

166,822

806,580

386,372

1,738,640

5.7.2 Evaluation of the Third Model: Intelligent Government County System That Use

Public Fog Nodes Distribution Model

5.7.2.1 Fifth Experiment: The impact of the di↵erent sets of a↵ected transactions on

various fog nodes number

The experiment was undertaken on the second model whereby the system has no

trusted fog node. This was attained through the employment of the transaction-dependency

graph system on both prototypes. The experiment’s main purpose was to assess the

performance of the damage assessment algorithm during the process of detecting the a↵ected

transactions in the absence of trusted fog node. As earlier described in section 3.6.3.1, the log

files created were based on transaction-dependency relationships that existed within

transactions and were additionally built at the same time as the local and global directed

graphs. For every existing log file, two variable graphs would be produced. One represents the

second model that does not have a trusted fog node (and absence of a global graph) in the

system utilized in the investigations present in section 5.6.

In order to enhance validity of the investigation, repetitive tests were conducted to

ensure fair comparisons of the outcomes from the two models, as depicted in investigations in

section 5.7.1 concerning trusted fog nodes. This was achieved by using a static number of fog

nodes accompanied by a dissimilar number of transactions in every log file. Then we insert the

same malicious transaction that was randomly entered for the first model, whereby the

a↵ected transactions also were grouped in three di↵erent sets or groups. The first group, fewer

than five a↵ected transactions were contained. The second group comprised of about ten to

fifteen transactions that were a↵ected, while the third grouping contained about thirty to

thirty-five transactions that were a↵ected and had been recognized. The average for each

group was determined in order to examine and appraise our approach. In order to define the

factor(s) impact (great or less) on the algorithms, a comparison of the results was conducted.

Figs.5.18, 5.19, 5.20, and 5.21 illustrate the correlation between the number of a↵ected

transactions, the number of transactions in each log file, and the average time required by our

system to detect all maliciously compromised transactions in the whole system. The average

time was calculated by averaging the detection time each fixed set of undamaged transactions

required.

The result shows that the smaller set of less than five a↵ected transactions took an

average of 0.076 milliseconds to 0.079 ms for discovery between the variables in log files and

fog nodes. That time almost doubled for the set containing 10 to 15 a↵ected transactions:

averaging 0.14 ms to 0.15 ms. The final set of 30 to 35 a↵ected transactions, claimed an average

of 0.31 ms to 0.39 ms. Therefore, the number of detected, compromised transactions has great

e↵ect on the total time the system remains unavailable. This applies in all cases, regardless of

the number of fog nodes or the number of transactions held by the log file.

5.7.2.2 Sixth Experiment: The impact of di↵erent number of transactions on various

number of fog nodes

Figures 5.22, 5.23, 5.24, and 5.25 demonstrate the relationship between the number of

transactions on each log file and the time requirement, averaged, for discovery of all a↵ected

transactions in the whole system. Overall, the results indicate that the number of transactions

does not have a significant impact on the total delay time which a↵ects system availability. But,

still, there is some small impact.

Figure 5.18: The impact of the di↵erent sets of a↵ected transactions on five fog nodes

Figure 5.19: The impact of the di↵erent sets of a↵ected transactions on ten fog nodes

0.37728

0.34385

0.39310

0.15616

0.14443

0.14833

0.07630

0.07676

0.07611

0.00000

0.05000

0.10000

0.15000

0.20000

0.25000

0.30000

0.35000

0.40000

0.45000

100

500

1000

Fog Nodes

Less than 5

10 -15

30 -35

0.33117

0.35589

0.34830

0.15947

0.13695

0.14261

0.07654

0.07817

0.07907

0.00000

0.05000

0.10000

0.15000

0.20000

0.25000

0.30000

0.35000

0.40000

100

500

1000

Fog Nodes

Less than 5

10 -15

30 -35

15 Fog Nodes

0.35000

0.32287

0.33020

0.30000

0.25000

0.20000

0.15000

0.10000

0.05000

0.00000

100 T 500 T 1000 T

Less than 5 10 -15 30 -35

0.31979

0.15296

0.14012

0.14377

0.07912

0.07944

0.07751

Figure 5.20: The impact of the di↵erent sets of a↵ected transactions on fifteen fog nodes

20 Fog Nodes

0.35000

0.32247

0.32710

0.32713

0.30000

0.25000

0.20000

0.15000

0.10000

0.05000

0.00000

100 T 500 T 1000 T

Less than 5 10 -15 30 -35

0.14435

0.14233

0.13383

0.07690

0.07864

0.07894

Figure 5.21: The impact of the di↵erent set of a↵ected transactions on twenty fog nodes For

example, in the experiment utilizing the set of less than five a↵ected transactions, the log file

of 100 transactions claimed less delay time than the larger log files by almost 0.001 ms to 0.002

ms.

On the other hand, the set of 10 to 15 a↵ected transactions in the log file of 100

transactions demanded more time than the larger log files by 0.01 ms. All other scenarios,

either with a di↵erent number of fog nodes in the system or a di↵erent set of a↵ected

transactions, o↵ered similar results.

Figure 5.22: The impact of di↵erent number of transactions on five fog nodes

5.7.2.3 Seventh Experiment: The impact of a di↵erent number of transactions and fog

nodes on di↵erent sets of a↵ected transactions

Figs. 5.26, 5.27 and 5.28 illustrate the impact of a variable number of transactions on

log file and a variable number of fog nodes. The sets of a↵ected transactions used in this

0.07630

0.15616

0.37728

0.07676

0.14443

0.34385

0.07611

0.14833

0.39310

0.00000

0.05000

0.10000

0.15000

0.20000

0.25000

0.30000

0.35000

0.40000

0.45000

LESS THAN 5

Number of affected transactions

Fog Nodes

100

500

1000

Figure 5.23: The impact of di↵erent number of transactions on ten fog nodes

Figure 5.24: The impact of di↵erent number of transactions on fifteen fog nodes

0.07654

0.15947

0.33117

0.07817

0.13695

0.35589

0.07907

0.14261

0.34830

0.00000

0.05000

0.10000

0.15000

0.20000

0.25000

0.30000

0.35000

0.40000

LESS THAN 5

Number of affected transactions

Fog Nodes

100

500

1000

0.07751

0.15296

0.31979

0.07912

0.14012

0.32287

0.07944

0.14377

0.33020

0.00000

0.05000

0.10000

0.15000

0.20000

0.25000

0.30000

0.35000

LESS THAN 5

Number of affected transactions

Fog Nodes

100

500

1000

Figure 5.25: The impact of di↵erent number of transactions on twenty fog nodes

experiment were fixed as previously established.

Fig. 5.26 indicates the set of a↵ected transactions as less than five. The time needed for

our damage assessment algorithm to detect all a↵ected transactions increased when the

number of fog nodes increased. This scenario held true regardless of log file size.

The delay that occurred here can be attributed to two primary determinants. First, a

small log file will impact fewer fog nodes than a large log file. Secondly, the local graphs expand

with a rise in transaction dependency. We observed the local graphs in this model increasing

in size with both the number of transactions on each log file and the number of fog nodes. We

also observed that the number of transactions in each log file had little impact on the results.

Hence, the larger log files of 1000 and 500 transactions took only slightly more time than those

of 100 transactions when we used the set of less than five a↵ected

transactions.

0.07690

0.14435

0.32247

0.07864

0.14233

0.32710

0.07894

0.13383

0.32713

0.00000

0.05000

0.10000

0.15000

0.20000

0.25000

0.30000

0.35000

LESS THAN 5

Number of affected transactions

Fog Nodes

100

500

1000

However, the results di↵ered, as seen in Fig. 5.27, when the a↵ected transactions set

was fixed at 10 to 15. Here we see in log files of 100 and 1000 transactions that an increase in

the number of fog nodes decreases the delay time. Also, the log file of 100 transactions involves

more time than the larger log files of 1000 and 500 transactions. But the time is slightly

decreased when the number of fog nodes increases. Generally, what we found is that the larger

set of a↵ected transactions extends on the local graph levels with a small log file and fewer fog

nodes. This explains the greater delay found in this configuration than in that of the graphs

with large log files and more fog nodes.

Thus, the log files of 1000 and 500 transactions perform better than the log file of 100

transactions for two reasons. First, because all a↵ected transactions in the system with the

largest of the log files could be found in perhaps one or two levels of the a↵ected graph, but

with the smaller log file the damage could be found in more than two levels of the a↵ected

graphs. Second, with the smaller log file the damage will a↵ect more fog nodes and that means

more graphs are scanned.

Additionally, in this set of a↵ected transactions, the log file of 500 transactions performs

much better than the log file of 1000 transactions because the graph size of 1000 transactions

is much larger than the graph size of 500 transactions and necessitates more time to locate a

malicious transaction on the graph.

The set of 30 to 35 a↵ected transactions produced di↵erent findings as seen in Fig. 5.28.

The log file of 500 transactions exhibited the same behavior in processing this set as it did in

the previous set of 10 to 15 a↵ected transactions. Where the number of fog nodes is five, this

log file showed better performance compared to the other two log files. Then, the delay time

decreased a bit for the log files of 100 and 1000 transactions when the number of fog nodes

increased to 10. All the log files at 15 fog nodes closed the gap, and then remained constant

and close at 20 fog nodes. As explained previously, the growth on the graph size, the increase

in the level of a↵ected transactions on the graphs, and the number of fog nodes that have been

a↵ected, have almost the same impact on the delay time.

Figure 5.26: The impact of a di↵erent number of transactions and fog nodes on a set of less

than five a↵ected transactions

5.7.2.4 Eighth Experiment: Cost of Resource Requirements

The space needed for the storage of local graph files on every fog node is shown in Table

5.5. A growth in the size of the local graph files is a result of an increase in the number of

transactions in the fog nodes or rather an augmentation of the number of fog nodes. However,

our experiment’s largest graph file was about 15847 kilobytes, which would be considered as

0.07400

0.07500

0.07600

0.07700

0.07800

0.07900

0.08000

Nodes

Less Than 5 Affected Transactions

100

500

1000

a small size and would, therefore not result in any problems related to space. This makes the

solution derived from the investigation inexpensive because of

Figure 5.27: The impact of di↵erent number of transactions and fog nodes on set of ten to

fifteen a↵ected Transactions

0.12000

0.12500

0.13000

0.13500

0.14000

0.14500

0.15000

0.15500

0.16000

0.16500

Nodes

Affected Transactions

100

500

1000

0.00000

0.05000

0.10000

0.15000

0.20000

0.25000

0.30000

0.35000

0.40000

0.45000

Nodes

Affected Transactions

100

500

1000

Figure 5.28: The impact of a di↵erent number of transactions and fog nodes on a set of 30 -35

a↵ected Transactions

its space, because it would not require massive storage needs, making it appropriate for

application.

Table 5.5: Storage requirement in Bytes for local graph files with absence of trusted fog node

Number Of Fog Nodes

Storage Requirement In Bytes

100

Transactions

500

Transactions

1000

Transactions

677

6,594

15,254

683

6,822

15,392

681

6,852

15,491

695

7104

15,847

5.7.3 Ninth Experiment: Comparison between having trusted fog node and

not:

We performed this experiment to show the di↵erence between two models: the model

with a trusted fog node (global graph) present in the system and another where there is no

trusted fog node in the system (no global graph) Which is the better performing of the two,

and under which factors? Figs. 5.29, 5.30, and 5.31 show the overall comparison between these

models on the average runtime. The result, illustrated by Fig. 5.29, indicates that the second

model, where there is no trusted fog node, performs better, in terms of execution time, with

the set of less than five a↵ected transactions in almost all cases by 0.001 - 0.002 ms. The

explanation for that lies in the use of the global graphs. The first model uses the global graphs

as input for the algorithm and those graphs are larger than the local graphs that are used as

input for the second model. Also the damage caused by the small set of less than five a↵ected

transactions will usually not a↵ect many fog nodes. On average only one to two fog nodes will

be a↵ected. The second model stands out a bit from the first model in

this case.

However, as seen in Figs. 5.30, and 5.31, the results di↵ered for the two larger sets of

a↵ected transactions. We observed that the model with a trusted fog node required less time

than the model without a trusted fog node by an average of 0.018 ms on the set of 10 to 15

a↵ected transactions. And it is faster than the model that has no trusted fog node by an average

of 0.07 ms on the set of 30 to 35 a↵ected transactions. This is the result of the damage sustained

with the larger set which could a↵ect a greater number of fog nodes. The second model is

required to scan the graph of each a↵ected fog node where the first model needs to only scan

the global graph.

In conclusion, the system benefits from having a trusted fog node when an attack

compromises the database and damage spreads to more than five transactions. Further, the

presence of the global graphs in the system stabilizes the results and speeds the detection

process, minimizing the system’s unavailability.

Students also viewed