Method and system for secure scheduling of workflows and virtual machine utilization in cloud
Scheduling of tasks in workflow comprises of heterogeneous and interdependent computational tasks. The method receives a set of workflows comprising of one or more heterogeneous tasks. Further, a set of parameters are extracted from each heterogeneous task to select a set of optimal virtual machines (VM) type combination parameters and a set of security level combination parameters. The method selects the optimized combination of VM types, security service levels and task order. Further, a workflow schedule is generated for the tasks of the selected VM type combinations. The method further performs optimal selection of VM types and security services, with efficient schedule generation, and effectively reuses VM with reduced overall cost without delay in make span. Additionally, the method enhances security model with accurate risk estimation.
1 . A processor implemented method for secure scheduling of workflows and virtual machine utilization in cloud, comprising:
receiving, from a user via one or more hardware processors, a set of workflows comprising of one or more heterogeneous tasks;
extracting, from each heterogeneous task via the one or more hardware processors, a set of parameters comprising of a workload, a transfer bandwidth, an output data size, a task type, a virtual machine (VM) renting cost, and a security level requirement;
selecting, from the set of parameters of each heterogeneous task via the one or more hardware processors, a set of optimal VM type combination parameters and a set of security level combination parameters and ordering of set of tasks with same start timing using a combinatorial optimization technique;
generating, for the one or more heterogeneous tasks via the one or more hardware processors, a schedule for each VM type combination parameters that keeps a risk rate of the workflow below a permissible limit while estimating risk to provide optimal combination of the set of security level combination parameters for each task without violation of a risk rate constraint by,
computing, using a start time based sorting technique, a set of timing parameters from at least one of (i) the set of optimal VM type and security level combination parameters, and the set of parameters, and (ii) sorting each heterogeneous task based on a start order of initial start time and capturing information of currently utilized VM for cost optimization, and
allocating, using a task VM allocation technique, each heterogeneous task with the set of optimal VM type combination and security level combination by computing a time execution cost (TEC) and a total execution time (TET) based on the set of timing parameters, wherein a task risk probability of each heterogeneous task is computed using an exponential function of average arrival rate of current security threat per time slot (λ), a difference between a required security level
(
s
r
i
l
)
and a provided security level
(
s
l
i
l
)
for the heterogeneous task, and time slot per hour, and the processing time of heterogeneous task on the VM type, given by:
P
(
t
i
,
sl
i
l
)
=
1
-
exp
(
-
λ
l
(
sr
i
l
-
sl
i
l
)
N
(
t
i
)
)
wherein N(t i ) is number of time slots, wherein each slot is an hour for which t i is executed on the VMs,
wherein a risk probability of all the security level requirements is computed using the task risk probability value given by:
P
(
t
i
)
=
1
-
∏
l
∈
{
a
,
g
,
c
}
(
1
-
P
(
t
i
,
sl
i
l
)
)
,
and
wherein the total risk rate of all the security level requirements are computed using the risk probability by linearizing risk rate constraints when the total risk rate of all the security level requirements are less than or equal to optimization constraints given by:
P
(
T
)
=
1
-
∏
t
i
∈
T
(
1
-
P
(
t
i
)
)
wherein the value of P(T) must be lower than the risk rate threshold P c (P c ∈[0, 1]), which is the permissible risk rate of the workflow given by:
∑
t
i
∈
T
∑
l
∈
{
a
,
g
,
c
}
-
λ
l
(
sr
i
l
-
sl
i
l
)
N
(
t
i
)
)
≥
log
(
1
-
P
c
)
,
number of hours for each task to use the VM is less than or equal to one N (t i ), wherein N (t i ) acts as a correction factor to prevent under estimation of risk and where ‘a’ represents authentication service, ‘g’ represents integrity service, and ‘c’ represents confidentiality service; and
executing, via one or more hardware processors, each heterogenous task of the workflow according to the generated schedule.
2 . The processor implemented method as claimed in claim 1 , wherein the set of timing parameters comprises of a start time (ST), an end time (ET), an index array (ID) listing an index of one or more heterogeneous task, a start time array (ST[⋅]), and an end time array (ET[⋅]).
3 . The processor implemented method as claimed in claim 2 , wherein the start time based sorting technique comprises:
obtaining the set of VM type combination and the set of parameters and initialize the index array for storing the start order of each heterogenous task;
computing for each heterogeneous task (i) a total transfer time (TT), (ii) an execution time (EXT), and (iii) a security overhead (SC);
updating the start time array (ST[⋅]) of each heterogeneous task with maximum end time array (ET[j]) of its predecessor task and store in the start time array (ST[⋅]);
computing the end time array (ET[⋅]) which is the sum of start time array (ST[⋅]) and a total processing time (PT), wherein the total processing time is the sum of the security overhead (SC), execution time (EXT), and the total transfer time (TT);
updating a start time reserve array (STT) with the start time array (ST[⋅]) value and an end time reserve array (ET r ) with the end time array ET[⋅]); and
sorting the start time (ST), the end time (ET), and the index array (ID) based on sorted order of start time.
4 . The processor implemented method as claimed in claim 1 , wherein the task VM allocation technique comprises:
initializing zeros for the total execution time and an idle time array (IT) for storing information;
searching for unutilized optimal VM type processed for prior heterogeneous task and is currently available to process next heterogeneous task with low VM renting cost and idle time, (i) if the heterogeneous task reuses the VM type used by corresponding predecessor task VM renting cost reduction is available with idle time and data transfer cost is excluded, and (ii) if the heterogeneous task reuses the VM type used by corresponding non-predecessor task VM renting cost reduction is for only available idle time;
renting a new VM type for each heterogeneous task when reusable VM type is unidentified;
computing a new idle time for the current heterogeneous task which reuses the VM type used by the prior heterogeneous task, and update idle time array (IT[j]) for the current heterogeneous task with an identifier and the new idle time array with current heterogeneous task (IT[i]);
computing for each heterogeneous task, the total execution cost, the total execution time, a task risk probability, a risk probability, and a total risk rate;
incrementing the total execution cost for the workflow for processing the current heterogeneous task by updating the data transfers;
sorting the end time, the index array and the start time and compute the total execution cost for the one or more heterogeneous task based on maximum end time; and
computing the end time based on summing the start time with the difference value of the end time array and the start time array.
5 . The processor implemented method as claimed in claim 4 , wherein the total execution cost is computed based on the difference value between the start time and the end time.
6 . The processor implemented method as claimed in claim 4 , wherein the total execution time is computed based on the maximum end time duration of each heterogeneous task.
7 . A system for secure scheduling of workflows and virtual machine utilization in cloud comprising:
a memory storing instructions;
one or more communication interfaces; and
one or more hardware processors coupled to the memory via the one or more communication interfaces, wherein the one or more hardware processors are configured by the instructions to:
receive a set of workflows comprising of one or more heterogeneous tasks;
extract from each heterogeneous task, a set of parameters comprising of a workload, a transfer bandwidth, an output data size, a task type, a virtual machine (VM) renting cost, and a security level requirement;
select from the set of parameters of each heterogeneous task, a set of optimal VM type combination parameters and a set of security level combination parameters using a combinatorial optimization technique;
generate for the one or more heterogeneous tasks, a schedule for each VM type combination parameters that keeps a risk rate of the workflow below a permissible limit while estimating risk to provide optimal combination of the set of security level combination parameters for each task without violation of a risk rate constraint by,
computing using a start time based sorting technique, a set of timing parameters from at least one of (i) the set of optimal VM type combination parameters, and the set of parameters, and (ii) sorting each heterogeneous task based on a start order of initial start time and capturing information of currently utilized VM for cost optimization, and
allocating using a task VM allocation technique, each heterogeneous task with the set of optimal VM type combination by computing a time execution cost (TEC) and a total execution time (TET) based on the set of timing parameters, wherein a task risk probability of each heterogeneous task is computed using an exponential function of average arrival rate of current security threat per time slot (λ), a difference between a required security level
(
sr
i
l
)
and a provided security level
(
sr
i
l
)
the heterogeneous task, and time slot per hour, and the processing time of heterogeneous task on the VM type, given by:
P
(
t
i
,
sl
i
l
)
=
1
-
exp
(
λ
l
(
sr
i
l
-
sl
i
l
)
N
(
t
i
)
)
wherein N(t i ) is number of time slots, wherein each slot is an hour for which t i is executed on the VMs,
wherein a risk probability of all the security level requirements is computed using the task risk probability value given by:
P
(
t
i
)
=
1
-
∑
l
∈
{
a
,
g
,
c
}
(
1
-
P
(
t
i
,
sl
i
l
)
)
,
wherein the total risk rate of all the security level requirements are computed using the risk probability by linearizing risk rate constraints when the total risk rate of all the security level requirements are less than or equal to optimization constraints given by:
P
(
T
)
=
1
-
∏
t
i
∈
T
(
1
-
P
(
t
i
)
)
wherein the value of P(T) must be lower than the risk rate threshold P c (P c ∈[0, 1]), which is the permissible risk rate of the workflow given by:
∑
t
i
∈
T
∑
l
∈
{
a
,
g
,
c
}
-
λ
l
(
sr
i
l
-
sl
i
l
)
N
(
t
i
)
)
≥
log
(
1
-
P
c
)
,
wherein
number of hours for each task to use the VM is less than or equal to one N (t i ), wherein N (t i ) acts as a correction factor to prevent under estimation of risk and where ‘a’ represents authentication service, ‘g’ represents integrity service, and ‘c’ represents confidentiality service; and
execute each heterogenous task of the workflow according to the generated schedule.
8 . The system of claim 7 , wherein the set of timing parameters comprises of a start time (ST), an end time (ET), an index array (ID) listing an index of one or more heterogeneous task, a start time array (ST[⋅]), and an end time array (ET[⋅]).
9 . The system of claim 8 , wherein the start time based sorting technique comprises:
obtain the set of VM type combination and the set of parameters and initialize the index array for storing the start order of each heterogenous task;
compute for each heterogeneous task, (i) a total transfer time (TT), (ii) an execution time (EXT), and (iii) a security overhead (SC);
update the start time array (ST[⋅]) of each heterogeneous task with maximum end time array (ET[j]) of its predecessor task and store in the start time array (ST[⋅]);
compute the end time array (ET[⋅]) which is the sum of start time array (ST[⋅]) and a total processing time (PT), wherein the total processing time is the sum of the security overhead (SC), execution time (EXT), and the total transfer time (TT);
update a start time reserve array (ST r ) with the start time array (ST[⋅]) value and an end time reserve array (ET r ) with the end time array ET[⋅]); and
sort the start time (ST), the end time (ET), and the index array (ID) based on sorted order of start time.
10 . The system of claim 7 , wherein the task VM allocation technique comprises:
initialize zeros for the total execution time and an idle time array (IT) for storing information;
search for unutilized optimal VM type processed for prior heterogeneous task and is currently available to process next heterogeneous task with low VM renting cost and idle time, (i) if the heterogeneous task reuses the VM type used by corresponding predecessor task VM renting cost reduction is available with idle time and data transfer cost is excluded, and (ii) if the heterogeneous task reuses the VM type used by corresponding non-predecessor task VM renting cost reduction is for only available idle time;
rent a new VM type for each heterogeneous task when reusable VM type is unidentified;
compute a new idle time for the current heterogeneous task which reuses the VM type used by the prior heterogeneous task, and update idle time array (IT[j]) for the current heterogeneous task with an identifier and the new idle time array with current heterogeneous task (IT[i]);
compute for each heterogeneous task, the total execution cost, the total execution time, a task risk probability, a risk probability, and a total risk rate;
increment the total execution cost for the workflow for processing the current heterogeneous task by updating the data transfers;
sort the end time, the index array and the start time and compute the total execution cost for the one or more heterogeneous task based on maximum end time; and
compute the end time based on summing the start time with the difference value of the end time array and the start time array.
11 . The system of claim 10 , wherein the total execution cost is computed based on the difference value between the start time and the end time.
12 . The system of claim 10 , wherein the total execution time is computed based on the maximum end time duration of each heterogeneous task.
13 . One or more non-transitory machine-readable information storage mediums comprising one or more instructions which when executed by one or more hardware processors cause:
receiving from a user a set of workflows comprising of one or more heterogeneous tasks;
extracting from each heterogeneous task, a set of parameters comprising of a workload, a transfer bandwidth, an output data size, a task type, a virtual machine (VM) renting cost, and a security level requirement;
selecting from the set of parameters of each heterogeneous task, a set of optimal VM type combination parameters and a set of security level combination parameters and ordering of set of tasks with same start timing using a combinatorial optimization technique;
generating for the one or more heterogeneous tasks, a schedule for each VM type combination parameters that keeps a risk rate of the workflow below a permissible limit while estimating risk to provide optimal combination of the set of security level
combination parameters for each task without violation of a risk rate constraint by, computing using a start time based sorting technique, a set of timing parameters from at least one of (i) the set of optimal VM type and security level combination parameters, and the set of parameters, and (ii) sorting each heterogeneous task based on a start order of initial start time and capturing information of currently utilized VM for cost optimization, and
allocating using a task VM allocation technique, each heterogeneous task with the set of optimal VM type combination and security level combination by computing a time execution cost (TEC) and a total execution time (TET) based on the set of timing parameters, wherein a task risk probability of each heterogeneous task is computed using an exponential function of average arrival rate of current security threat per time slot (λ), a difference between a required security level
(
sr
i
l
)
and a provided security level
(
sl
i
l
)
for the heterogeneous task, and time slot per hour, and the processing time of heterogeneous task on the VM type, given by:
P
(
t
i
,
sl
i
l
)
=
1
-
exp
(
λ
l
(
sr
i
l
-
sl
i
l
)
N
(
t
i
)
)
wherein N(t i ) is number of time slots, wherein each slot is an hour for which t i is executed on the VMs,
wherein a risk probability of all the security level requirements is computed using the task risk probability value given by:
P
(
t
i
)
=
1
-
∏
l
∈
{
a
,
g
,
c
}
(
1
-
P
(
t
i
,
sl
i
l
)
)
,
and
wherein the total risk rate of all the security level requirements are computed using the risk probability by linearizing risk rate constraints when the total risk rate of all the security level requirements are less than or equal to optimization constraints given by:
P
(
T
)
=
1
-
∏
t
i
∈
T
(
1
-
P
(
t
i
)
)
wherein the value of P(T) must be lower than the risk rate threshold P c (P c ∈[0, 1]), which is the permissible risk rate of the workflow given by:
∑
t
i
∈
T
∑
l
∈
{
a
,
g
,
c
}
-
λ
l
(
sr
i
l
-
sl
i
l
)
N
(
t
i
)
)
≥
log
(
1
-
P
c
)
,
wherein
number of hours for each task to use the VM is less than or equal to one N (t i ), wherein N(t i ) acts as a correction factor to prevent under estimation of risk and where ‘a’ represents authentication service, ‘g’ represents integrity service, and ‘c’ represents confidentiality service; and
executing each heterogenous task of the workflow according to the generated schedule.
14 . The one or more non-transitory machine-readable information storage mediums of claim 13 , wherein the set of timing parameters comprises of a start time (ST), an end time (ET), an index array (ID) listing an index of one or more heterogeneous task, a start time array (ST[⋅]), and an end time array (ET[⋅]).