Rodrigo A P Silva

Esther Pacitti
email: esther.pacitti@inria.fr

Yuri Frota

Daniel De Oliveira
email: danielcmo@ic.uff.br

Análise de Desempenho da Distribuic ¸ão de Workflows Científicos em Nuvens com Restric ¸ões de Confidencialidade *

Clouds provide an on-demand environment that allows scientists to migrate their local experiments to an elastic environment. Experiments are modeled as scientific workflows, and many of them are computing and data-intensive. The storage of these data is a concern, as confidentiality can be compromised. Malicious users may infer knowledge of the results and structure of workflows. Data dispersion and encryption can be adopted to increase confidentiality, but these mechanisms cannot be adopted uncoupled from workflow scheduling, at the risk of increasing execution time and financial costs. In this paper, we present SaFER (workflow Scheduling with conFidEntity pRoblem), a scheduling approach that considers data confidentiality constraints.

Introduc ¸ão

Os workflows científicos (doravante denominados apenas como workflows) são um arcabouc ¸o para modelar as etapas de uma simulac ¸ão científica [START_REF] De Oliveira | Data-Intensive Workflow Management: For Clouds and Data-Intensive and Scalable Computing Environments[END_REF]]. Essas etapas envolvem a execuc ¸ão de múltiplas aplicac ¸ões com parâmetros de entrada e de saída. Os workflows são modelados como grafos dirigidos, nos quais os nós representam as atividades (i.e., associadas à um programa, script, etc.) e os arcos representam as dependências de dados entre as atividades [START_REF] Deelman | Pegasus, a workflow management system for science automation[END_REF]. Denominamos ativac ¸ão a execuc ¸ão de uma atividade que consome um dado específico (de entrada ou produzido pelo próprio workflow). Esses workflows geralmente são modelados e executados usando mecanismos complexos chamados de Sistemas de Gerência de Workflows (SGWfs). Os SGWfs apoiam a composic ¸ão, a execuc ¸ão, o monitoramento e a captura de dados de proveniência [START_REF] Freire | Provenance for Computational Tasks: A Survey[END_REF]] (histórico de execuc ¸ões para fins de reprodutibilidade) dos workflows. Em muitos domínios da ciência, como a biologia, a química e a astronomia [START_REF] De Oliveira | Data-Intensive Workflow Management: For Clouds and Data-Intensive and Scalable Computing Environments[END_REF]] é comum que um mesmo workflow seja executado múltiplas vezes até que o cientista possa confirmar ou refutar uma hipótese. Essas múltiplas execuc ¸ões, aliadas ao grande volume de dados a ser processado, requerem ambientes de processamento de alto desempenho ou de processamento escalável em uso de dados, como clusters de máquinas commodity e supercomputadores, para que os workflows produzam resultados em tempo hábil [START_REF] Deelman | Pegasus, a workflow management system for science automation[END_REF].

Muitos cientistas migraram seus workflows para nuvens [START_REF] González | A break in the clouds: towards a cloud definition[END_REF]], uma vez que as nuvens de computadores oferecem uma ampla variedade de recursos sob demanda, desde máquinas virtuais (VMs), áreas de armazenamento, etc. Além disso, as nuvens oferecem elasticidade, o que pode ser valioso para a execuc ¸ão de workflows em larga escala. Muitos SGWfs permitem a execuc ¸ão de workflows em nuvens como o Pegasus [START_REF] Deelman | Pegasus, a workflow management system for science automation[END_REF] e o SciCumulus [START_REF] De Oliveira | Scicumulus: A lightweight cloud middleware to explore many task computing paradigm in scientific workflows[END_REF]. Para permitir a execuc ¸ão dos workflows de forma otimizada, cada ativac ¸ão necessita ser escalonada para uma VM. Logo, o problema de escalonamento se torna decidir em qual VM executar cada uma das ativac ¸ões do workflow. O escalonamento de ativac ¸ões de workflows é um conhecido problema NP-Difícil. Os SGWfs já oferecem uma série de algoritmos de escalonamento que exploram características das nuvens. Ao executar workflows na nuvem, os SGWfs existentes comumente se baseiam em áreas de armazenamento compartilhado para gravar os dados produzidos (e.g., chamaremos essas áreas de buckets), e.g., o Pegasus provê mecanismos para armazenar dados no Amazon S3. Da mesma forma, o SciCumulus usa o s3fs3 (sistema de arquivos compartilhado sobre o S3) para armazenamento e recuperac ¸ão de dados. Embora a utilizac ¸ão de servic ¸os de armazenamento na nuvem facilite a gerência dos dados produzidos e consumidos de um workflow, a confidencialidade dos resultados é ainda uma questão aberta [START_REF] Ennajjar | Securing data in cloud computing by classification[END_REF]]. Nos últimos anos, muitos cientistas evitaram migrar seus experimentos para a nuvem por questões de confidencialidade. Os arquivos produzidos e consumidos por um workflow podem conter dados confidenciais, e, se os mesmos forem armazenados em conjunto e um usuário malicioso tiver acesso ao bucket, o mesmo pode inferir seus resultados, o que não é desejável.

Para ilustrar esse problema, consideremos um fragmento do workflow Montage [START_REF] Deelman | Pegasus, a workflow management system for science automation[END_REF], apresentado na Figura 1. O Montage cria uma imagem em mosaico a partir de múltiplas imagens astronômicas menores. Apesar do Montage possuir 10 atividades, na Figura 1, apresentamos somente duas (mProjectPP, em azul, e mDiff-Fit, em amarelo). Cada atividade possuem ativac ¸ões associadas, cada uma consumindo arquivos de entrada diferentes. Por exemplo, três ativac ¸ões de mProjectPP são apresentadas na Figura 1 (ID00000, ID00001 e ID00002), cada uma consumindo arquivos de entrada diferentes (somente region.hdr é consumido pelas três ativac ¸ões). Os arquivos p2mass-atlas-ID00000s-jID00000 area.fits e p2mass-atlas-ID00000s-jID00000.fits são gerados pela ativac ¸ão ID00000 (da atividade mProjectPP), que por sua vez consome os arquivos region.hdr e 2mass-atlas-ID00000s-jID00000.fits. Caso os dois arquivos produzidos sejam armazenados em conjunto com os arquivos de entrada, um usuário malicioso pode inferir que tipo de transformac ¸ão foi aplicada nos dados. Logo, p2mass-atlas-ID00000s-jID00000 area.fits e p2mass-atlas-ID00000s-jID00000.fits não devem ser armazenados em conjunto. Além disso, não devem ser armazenados em conjunto com os arquivos region.hdr e 2mass-atlas-ID00000s-jID00000.fits. Entretanto, nem todos os arquivos possuem restric ¸ões de armazenamento entre si. Por exemplo, os arquivos p2mass-atlas-ID00000s-jID00000 area.fits e p2mass-atlas-ID00000s-jID00000.fits podem ser armazenado em conjunto com o arquivo p2mass-atlas-ID00000s-jID00001 area.fits, pois não foram gerados pela mesma ativac ¸ão, e nem a partir dos mesmos arquivos de entrada. Essa definic ¸ão de quais arquivos serão armazenados em conjunto em um bucket se dá o nome de plano de dispersão. De fato, a dispersão é uma das principais técnicas para garantir confidencialidade de dados em nuvens [START_REF] Branco-Jr | A new mechanism to preserving data confidentiality in cloud database scenarios[END_REF]. As restric ¸ões de armazenamento necessárias para gerar um plano de dispersão podem ser representadas como um grafo de conflito (Figura 1(à direita)), onde cada arco ligando dois arquivos representa um conflito (i.e., esses dois arquivos não devem ser armazenados no mesmo bucket). Um bom plano de dispersão de dados deve considerar conflitos entre os arquivos e a capacidades/custo de armazenamento nos buckets. Abordagens existentes já tratam do problema de dispersão de dados para garantir a confidencialidade [START_REF] Guerine | A provenance-based heuristic for preserving results confidentiality in cloud-based scientific workflows[END_REF]]. Porém, tais abordagens dispersam os dados desacoplados do escalonamento das ativac ¸ões do workflow na nuvem. Essa dispersão sem considerar a VM que a ativac ¸ão que consumirá os dados irá executar, pode inserir um overhead de transferência desnecessário, e.g., um arquivo pode ser armazenado em um bucket da Amazon S3 em São Paulo e a ativac ¸ão que o consome executar no Japão. Logo, o plano de dispersão dos dados integrado ao escalonamento das ativac ¸ões é fundamental. Além disso, [START_REF] Branco-Jr | A new mechanism to preserving data confidentiality in cloud database scenarios[END_REF]] mencionam que a criptografia nas VMs aumenta o nível de seguranc ¸a nos dados, e devem ser consideradas complementarmente ao plano de dispersão.

Nesse artigo, de forma a garantir a confidencialidade dos dados produzidos e ao mesmo tempo reduzir o tempo total e o custo de execuc ¸ão do workflow, propomos uma abordagem denominada SaFER (workflow Scheduling with conFidEntiality pRoblem) para escalonamento de workflows, que leva em considerac ¸ão a variedade e a heterogeneidade de VMs na nuvem (por exemplo, diferentes larguras de banda, taxas de transferência e capacidades de processamento), os mecanismos de seguranc ¸a oferecidos por cada VM (e.g., criptografia) e o grafo de conflito entre os arquivos, todos integrados. Assim, o escalonador do SGWf define a distribuic ¸ão de ativac ¸ões nas VMs e o plano de dispersão dos arquivos entre os múltiplos buckets minimizando o tempo total de execuc ¸ão e a chance de um usuário malicioso acessar os dados e inferir o resultado do experimento. As contribuic ¸ões do presente artigo são: (i) a formulac ¸ão do problema SaFER como um problema de programac ¸ão matemática mista, (ii) a definic ¸ão de um algoritmo de escalonamento de workflows com restric ¸ões de confidencialidade, e (iii) uma avaliac ¸ão experimental da abordagem proposta usando benchmarks tradicionais da área de workflows científicos. Esse artigo está organizado em cinco sec ¸ões além desta introduc ¸ão. Na Sec ¸ão 2 apresentamos os trabalhos relacionados. Na Sec ¸ão 3 é apresentada a formulac ¸ão matemática, e na Sec ¸ão 4 a heurística de escalonamento proposta. Na Sec ¸ão 5, discutimos a avaliac ¸ão experimental, e na Sec ¸ão 6 concluímos o presente artigo.

Trabalhos Relacionados

O escalonamento de ativac ¸ões de workflows em nuvem é um tópico amplamente discutido na literatura. Existem diversas abordagens de escalonamento que consideram tempo de transferência, custo financeiro, reduc ¸ão de makespan, etc. [START_REF] Liu | A survey of data-intensive scientific workflow management[END_REF]]. Entretanto, poucas abordagens focam no escalonamento de workflows considerando questões de confidencialidade e/ou seguranc ¸a [START_REF] Sujana | Smart pso-based secured scheduling approaches for scientific workflows in cloud computing[END_REF][START_REF] Abazari | Mows: multi-objective workflow scheduling in cloud computing based on heuristic algorithm[END_REF][START_REF] Tawfeek | Service flow management with multiobjective constraints in heterogeneous computing[END_REF][START_REF] Shishido | Multi-objective optimization for workflow scheduling under task selection policies in clouds[END_REF][START_REF] Guerine | A provenance-based heuristic for preserving results confidentiality in cloud-based scientific workflows[END_REF]. A abordagem OPTIC [START_REF] Guerine | A provenance-based heuristic for preserving results confidentiality in cloud-based scientific workflows[END_REF] propõe uma heurística para dispersão de dados produzidos por workflows em buckets de provedores de nuvem. Apesar de representar um avanc ¸o no que tange questões de confidencialidade de dados, a OPTIC não considera o escalonamento do workflow para planejar a dispersão dos dados, i.e., um dado pode ser armazenado em um bucket geograficamente distante da VM em que será processado. Isso pode ser um problema tanto em termos de makespan (já que o tempo de transferência será impactado) quanto em termos financeiros (custos de transferência e pagamento do tempo em que a VM se mantém inativa aguardando a transferência dos dados.

Por outro lado, existem trabalhos que propõem algoritmos de escalonamento de workflows que consideram questões de seguranc ¸a no processo. [START_REF] Shishido | Multi-objective optimization for workflow scheduling under task selection policies in clouds[END_REF] propõem uma abordagem de escalonamento de workflows em nuvem que considera restric ¸ões de níveis de seguranc ¸a para as VMs envolvidas na execuc ¸ão, i.e., o algoritmo só executa determinadas ativac ¸ões em VMs que oferecem os requisitos de seguranc ¸a necessários. Apesar de ser um avanc ¸o [START_REF] Shishido | Multi-objective optimization for workflow scheduling under task selection policies in clouds[END_REF]] não consideram questões de dispersão de dados, i.e., o requisito de seguranc ¸a é considerado no processamento da ativac ¸ão, mas não onde os dados são armazenados. De forma similar, [START_REF] Tawfeek | Service flow management with multiobjective constraints in heterogeneous computing[END_REF] resolve o problema de escalonamento de workflows em nuvem por meio de um algoritmo genético que considera as restric ¸ões de seguranc ¸a, prazo e custo. Assim como o trabalho de [START_REF] Shishido | Multi-objective optimization for workflow scheduling under task selection policies in clouds[END_REF], as restric ¸ões de seguranc ¸a não consideram questões de armazenamento de dados. [START_REF] Sujana | Smart pso-based secured scheduling approaches for scientific workflows in cloud computing[END_REF]] e [START_REF] Abazari | Mows: multi-objective workflow scheduling in cloud computing based on heuristic algorithm[END_REF] propõem abordagens de escalonamento multi-critério que consideram as demandas de seguranc ¸a das ativac ¸ões e as interac ¸ões na distribuic ¸ão de ativac ¸ões seguras na nuvem. De maneira complementar, o i-OBJECT é uma abordagem que visa aumentar o nível de confidencialidade dos dados usando fragmentac ¸ão, decomposic ¸ão e dispersão de informac ¸ões para dividir os dados em partes irreconhecíveis e armazená-los hosts distribuídos na nuvem [START_REF] Branco-Jr | A new mechanism to preserving data confidentiality in cloud database scenarios[END_REF]].

Formulac ¸ão Matemática

O problema tratado pela abordagem SaFER pode ser definido como um problema de programac ¸ão matemática mista como descrito a seguir. Seja N o conjunto de ativac ¸ões de um workflow a serem executadas. Vamos definir M = M ∪ B como o conjunto de todos os recursos computacionais envolvidos na execuc ¸ão, onde M é o conjunto de todas as VMs com capacidade de processamento/armazenamento local, e B é o conjunto de buckets que possuem apenas capacidade de armazenamento (i.e., não processam dados). Cada VM j ∈ M possui uma capacidade de armazenamento máxima cm j e um custo financeiro de c M j (por unidade de tempo). Similarmente, cada bucket j ∈ B possui uma faixa de intervalos de uso de dados {0...|L j |}, onde cada intervalo l ∈ L j possui um tamanho sm jl e um custo financeiro de uso c B jl (L 0 representa que o bucket está vazio). Essa definic ¸ão de uso de intervalo de dados no bucket segue a organizac ¸ão de provedores como Amazon AWS e Azure. Vamos também definir D = D s ∪ D d como o conjunto de todos os dados produzidos/consumidos em uma execuc ¸ão do workflow, onde cada dado d ∈ D tem tamanho W (d) e pode ser tanto estático (D s ), previamente armazenado no seu recurso computacional de origem O(d) ∈ M (dados de entrada do workflow), ou dinâmico (D d ), i.e., o dado será gerado durante a execuc ¸ão do workflow. Além disso, para cada ativac ¸ão i ∈ N , definimos um conjunto de dados de entrada ∆ in (i) ⊆ D necessário para sua execuc ¸ão, e um conjunto de dados de saída ∆ out (i) ⊆ D d gerados pela execuc ¸ão da ativac ¸ão. Definimos também os requisitos do usuário c max como o custo financeiro máximo permitido (i.e., budget)), e t max como o tempo máximo de processamento do workflow (i.e., deadline), onde T = {1, . . . , t max } é definido como o conjunto de períodos de tempo. Denotamos t ij como o tempo de processamento da ativac ¸ão i ∈ N executada na VM j ∈ M . Similarmente, denotamos

- → t djp como o tempo gasto pela VM j ∈ M para ler o dado d ∈ D armazenado no recurso computacional p ∈ M , e ← - t djp como o tempo gasto pela VM j ∈ M para escrever o dado d ∈ D d no recurso computacional p ∈ M .
Em relac ¸ão aos requisitos de confidencialidade do workflow, definimos o grafo de conflito de dados (nesse artigo usamos arquivos como a unidade mínima, mas caso uma fragmentac ¸ão dos dados fosse aplicada, cada fragmento seria considerado um vértice do grafo) G c = (D, E h ∪ E s ), formado pelo conjunto de vértices (dados) D e o conjunto de arestas E h ∪ E s . O conjunto E h é definido como o conjunto de pares de dados (d 1 , d 2 ) onde d 1 ∈ D e d 2 ∈ D que não podem ser armazenados no mesmo recurso computacional por razões de confidencialidade. Similarmente, o conjunto de arestas E s é definido como o conjunto de pares de dados (d 1 , d 2 ) que se forem armazenados no mesmo recurso computacional, uma penalidade de confidencialidade p d 1 d 2 deve ser cobrada. Definimos também R como o conjunto dos requisitos de seguranc ¸a presentes nas ativac ¸ões do workflow, onde cada requisito r ∈ R pode variar de intensidade no intervalo {0...l r max }. Um requisito de seguranc ¸a pode ser a ativac ¸ão i ∈ N requisitar execuc ¸ões em VMs que oferec ¸am alto nível de criptografia (o nivel pode ser definido de acordo com as intensidades dos intervalos, explicadas a seguir). Dessa forma, definimos que cada ativac ¸ão i ∈ N possui uma necessidade de l ri task em relac ¸ão ao requisito r ∈ R, e que cada VM j ∈ M pode oferecer l rj vm de seguranc ¸a em relac ¸ão a este requisito (onde 0 ≤ l ri task , l rj vm ≤ l r max ). Dessa forma, podemos definir o grau de exposic ¸ão máxima de confidencialidade de um escalonamento como Indica o nível de exposic ¸ão da ativac ¸ão i ∈ N em relac ¸ão ao requisito de seguranc ¸a r ∈ R. q jl Contem a quantidade (tamanho) total de dados alocada no bucket j ∈ B no intervalo l ∈ L j . z T j Indica o tempo total de uso da VM j ∈ M . z T Indica o tempo total de processamento do workflow (makespan).

s max = r∈R |N | • l r max + (d 1 ,d 2 )∈Es p d 1 d 2 . A
A func ¸ão objetivo procura minimizar 3 fatores: o makespan (1), o custo financeiro (2) e o nível de exposic ¸ão de confidencialidade (3), onde os pesos α t , α b e α s definem a relevância de cada um destes 3 objetivos, respectivamente. Além disso, o valor de cada um dos objetivos é normalizado por seus valores máximos definidos por t max , c max e s max respectivamente.

min α t • ( z T tmax )+ (1) α b • ( j∈M c M j z T j cmax + j∈B l∈L j c B jl q jl cmax ) (2) αs • ( r∈R i∈N e ri smax + (d 1 ,d 2 )∈Es p d 1 d 2 w d 1 d 2 smax ) (3)
As Restric ¸ões (4) garantem que cada ativac ¸ão será executada, enquanto que as Restric ¸ões (5) e ( 6) obrigam que cada operac ¸ão de leitura e escrita deve ser realizada.

j∈M t∈T

x ijt = 1, ∀i ∈ N (4) j∈M p∈M t∈T - → x idjpt = 1, ∀i ∈ N, ∀d ∈ ∆ in (i) (5) j∈M p∈M t∈T ← -x idjpt = 1, ∀i ∈ N, ∀d ∈ ∆ out (i) (6)
As Restric ¸ões (7) garantem que cada dado d ∈ ∆ out (i) só pode ser escrito, se a ativac ¸ão i foi executada anteriormente. Além disso, as Restric ¸ões (8) obrigam que cada dado d não possa ser escrito antes da execuc ¸ão da ativac ¸ão i (responsável por sua escrita).

← -x idjpt ≤ t-t ij q=1 x ijq , ∀i ∈ N, ∀d ∈ ∆ out (i), ∀j ∈ M, ∀p ∈ M , ∀t = (t ij + 1) • • • T M (7) ← -x idjpt = 0 ∀i ∈ N, ∀d ∈ ∆ out (i), ∀j ∈ M, ∀p ∈ M , 1 ≤ t ≤ t ij (8)
As Restric ¸ões (9) estabelecem que uma ativac ¸ão só pode ser executada se todas suas leituras de dados de entrada foram anteriormente concluídas.

x ijt ≤ p∈M t- - → t djp q=1 - → x idjpq , ∀i ∈ N, ∀d ∈ ∆ in (i), ∀j ∈ M, ∀t ∈ T, such (t - - → t djp ) ≥ 1 (9)
As Restric ¸ões (10) garantem que apenas uma ac ¸ão ativa (execuc ¸ão, leitura ou escrita) possa ser realizada em cada período de tempo em cada VM. Por outro lado, as Inequac ¸ões (11) definem que ac ¸ões passivas (um dado ser lido ou ser escrito) podem ser realizadas em paralelo. Note que se uma ac ¸ão (ativa ou passiva) é realizada por uma VM j no período t, a variável de contratac ¸ão v jt terá valor 1, indicando que a máquina está contratada.

i∈N t q=max (1,t-t ij +1) x ijq + i∈N d∈∆ out (i) p∈M t r=max (1,t- ← - t djp +1) ← -x idjpr + i∈N d∈∆ in (i) p∈M t r=max (1,t- - → t djp +1) - → x idjpr ≤ v jt , ∀j ∈ M, ∀t ∈ T (10) i∈N d∈∆ out (i) p∈M t r=max (1,t- ← - t dpj +1) ← -x idpjr + i∈N d∈∆ in (i) p∈M t r=max (1,t- - → t dpj +1) - → x idpjr ≤ |M |.v jt , ∀j ∈ M, ∀t ∈ T (11)
As Restric ¸ões (12) estabelecem que não existem dados dinâmicos gerados no início da execuc ¸ão, enquanto que as Restric ¸ões (13) e ( 14) estabelecem que os dados estáticos estão armazenados em seus respectivos recursos origem.

y dj1 = 0, ∀d ∈ D d , ∀j ∈ M (12) y dj1 = 0, ∀d ∈ Ds | j ∈ (M \O(d)) (13) y djt = 1, ∀d ∈ Ds | j ∈ O(d), ∀t ∈ T (14)
As Restric ¸ões (15) e ( 16) conectam as variáveis de armazenamento y com as variáveis de escrita ← -

x e as de leitura -→ x , garantindo uma leitura e escrita consistente com os dados armazenados tanto em VMs quanto em buckets (M ).

y dp(t+1) = y dpt + j∈M ← -x idjp(t- ← - t djp +1) , ∀d ∈ D, ∀p ∈ M , ∀t ∈ {1 . . . tmax -1}, such (t - ← - t djp + 1) ≥ 1 and d ∈ ∆ out (i) (15) j∈M - → x idjpt ≤ y dpt , ∀i ∈ N, ∀d ∈ ∆ in (i), ∀p ∈ M , ∀t ∈ T (16)
A capacidade de armazenamento das máquinas é limitado pelas Restric ¸ões (17). As Restric ¸ões (18) conectam a última operac ¸ão de escrita em cada máquina com a variável do tempo total de execuc ¸ão do workflow z T . Além disso, as Restric ¸ões (19) relacionam as variáveis de contratac ¸ão v jt e z T j com o objetivo de estabelecer o custo financeiro de cada VM j, enquanto que as Restric ¸ões (20) asseguram que os custos financeiros não ultrapassem o orc ¸amento máximo disponível.

d∈D y djt W (d) ≤ cm j , ∀j ∈ M , ∀t ∈ T (17) ← -x idjpt • (t + ← - t djp ) ≤ z T , ∀i ∈ N, ∀d ∈ ∆ out (i), ∀j ∈ M, ∀p ∈ M , ∀t ∈ T (18) v jt • t ≤ z T j , ∀j ∈ M, ∀t ∈ T (19) j∈M c M j z T j + j∈B l∈L j c B jl q jl ≤ cmax (20)
As seguintes restric ¸ões operacionais (21) precisam ser satisfeitas: uma ativac ¸ão i só pode iniciar sua execuc ¸ão se todos seus arquivos de entrada d ∈ ∆ in (i) já estiverem disponíveis para leitura.

p∈M - → x idjpt • |∆ in (i)| ≤ g∈∆ in (i) p∈M y gpt , ∀i ∈ N, ∀d ∈ ∆ in (i), ∀j ∈ M, ∀t ∈ T (21)
As Restric ¸ões ( 22) conectam as variáveis de armazenamento (temporais) y com as variáveis de armazenamento (atemporais) y. Restric ¸ões (23) asseguram que dados conflitantes não sejam armazenados no mesmo recurso) (arestas fortes). De forma similar, as Inequac ¸ões (24) garantem que se dois dados conflitantes são armazenados no mesmo recurso, a variável de penalizac ¸ão w terá valor 1 (arestas fracas). As Restric ¸ões (25) medem o nível de exposic ¸ão (risco) de se executar uma ativac ¸ão em relac ¸ão aos requisitos de seguranc ¸a.

y djt ≤ y dj , ∀d ∈ D, ∀j ∈ M , ∀t ∈ T (22) y d 1 j + y d 2 j ≤ 1 , ∀(d 1 , d 2 ) ∈ E h , ∀j ∈ M (23) y d 1 j + y d 2 j ≤ 1 + w d 1 d 2 , ∀(d 1 , d 2 ) ∈ Es, ∀j ∈ M (24) l ri task - j∈M t∈T l rj vm x ijt ≤ e ri , ∀i ∈ N, ∀r ∈ R (25)
As Equac ¸ões (26) definem o tamanho total dos dados armazenados em cada bucket. As Restric ¸ões ( 27) estabelecem que apenas um intervalo de armazenamento l ∈ L j é usado em cada bucket j ∈ B, enquanto as Restric ¸ões (28) limitam a quantidade de dados armazenados em cada intervalo no bucket. Note que as Restric ¸ões ( 27) e ( 29) estabelecem em qual intervalo de uso de dados (b jl ) o bucket se encontra, de acordo com a quantidade de dados total (q jl ) armazenada nele. Por fim, as Restric ¸ões (30) impõe que se um intervalo l ∈ L j \{0} do bucket j ∈ B está em uso, então deve existir pelo menos um dado armazenado no bucket j.

l∈L j q jl = d∈D y dj W (d)
, ∀j ∈ B (26)

l∈L j b jl = 1 , ∀j ∈ B (27) d∈D y dj W (d) ≤ l∈L j sm jl b jl , ∀j ∈ B (28) sm j(l-1) .b jl ≤ q jl ≤ sm jl .b jl , ∀j ∈ B, ∀l ∈ L j \{0} (29) b jl ≤ d∈D y dj , ∀j ∈ B, ∀l ∈ L j \{0} (30)

Abordagem Heurística para Escalonamento de Workflows com Restric ¸ões de Confidencialidade

O problema modelado na Sec ¸ão 3 pode ser resolvido por métodos exatos para instâncias pequenas (10 ativac ¸ões ou menos). Porém, são impraticáveis para instâncias do mundo real pois consomem muitos recursos computacionais elevando demasiadamente o tempo de execuc ¸ão. As Metaheurísticas são métodos que orquestram uma interac ¸ão entre procedimentos de melhorias locais e estratégias de nível superior para criar um processo capaz de escapar dos ótimos locais efetuando buscas no espac ¸o de soluc ¸ão [START_REF] Gendreau | Handbook of metaheuristics[END_REF]], apresentando-se como uma boa alternativa aos métodos exatos. Logo, propomos uma heurística construtiva gulosa e estocástica como parte da abordagem SaFER, denominada SaFER-hcg, para resolver o escalonamento de ativac ¸ões com restric ¸ão de confidencialidade. Nosso objetivo é encontrar boas soluc ¸ões para instâncias de grande porte.

No Algoritmo 1, construtivo, o lac ¸o mais externo (linha 2) itera até que todas as ativac ¸ões sejam executadas em alguma VM. Nesse lac ¸o, é criada uma Lista de Candidatos (LC) combinando cada ativac ¸ão ainda não escalonada i ∈ N com todas as VMs disponíveis j ∈ M (linhas 4 a 9). Porém, nem todas as ativac ¸ões estão prontas para serem adicionadas à LC porque dependem se as dependências de dados foram satisfeitas, i.e., se seus arquivos de entrada já estão disponíveis (linha 6). Para calcularmos o "custo" de cada candidato, o inserimos na soluc ¸ão atual S e calculamos o valor da func ¸ão objetivo (F O) descrita pelas Equac ¸ões (1-3). Dentro do cálculo da func ¸ão objetivo, definimos também os recursos computacionais W ⊆ M que irão armazenar os dados de saída da ativac ¸ão i da seguinte forma: para cada dado d ∈ ∆ out (i) selecionamos aleatoriamente β recursos computacionais dentre o conjunto M e escolhemos o de menor acréscimo ao valor da F O que não irá gerar inviabilidade em relac ¸ão às restric ¸ões de capacidade e confidencialidade para realizar a gravac ¸ão do dado. Em seguida, ordenamos a LC em func ¸ão do valor do custo (F O) de cada soluc ¸ão (linha 9) e criamos uma Lista Restrita de Candidatos (LRC) contendo os melhores candidatos usando o parâmetro α LRC (linha 10). Posteriormente, um candidato é selecionado aleatoriamente de LRC e adicionado ao escalonamento atual S (linhas 11 e 12). O procedimento é repetido até que todas as ativac ¸ões do workflow sejam escalonadas. Dadas as características aleatórias do algoritmo, o procedimento construtivo pode gerar diferentes soluc ¸ões para um mesmo dado de entrada, i.e., para uma mesma instância do workflow.

Em nossos experimentos, executamos o algoritmo da SaFER-hcg 100 vezes armazenando, sempre, o melhor resultado encontrado.

Algoritmo 1: Heurística Construtiva Gulosa-Aleatória SaFER-hcg

Dados: α LRC , β, α t , α b , αs, tmax , cmax Resultado: escalonamento S 1 S ← ∅, N ← N 2 enquanto N = ∅ fac ¸a 3 LC ← ∅ 4 para cada i ∈ N fac ¸a 5 para cada j ∈ M fac ¸a 6 se ∆ in (i) já foi gerado então 7 W, F O ← CalculaF O(S, i, j, tmax, cmax, β, α t , α b , αs) 8 LC ← LC ∪ (i, j, W ) 9 ordena LC por F O 10 LRC ← ListaRestritaDeCandidatos(LC, α LRC ) 11 (i * , j * , W * ) ← Sorteia(LRC) 12 S ← S ∪ (i * , j * , W * ) 13 N ← N \{i * } 14 retorna

Avaliac ¸ão Experimental

Nesta sec ¸ão, comparamos a soluc ¸ão heurística SaFER-hcg (Sec ¸ão 4) com a soluc ¸ão exata fornecida pelo modelo matemático (i.e., baseline). Para compararmos as soluc ¸ões, foram criadas 9 instâncias sintéticas de execuc ¸ões de workflows, pequenas o suficiente para que o método exato encontre alguma soluc ¸ão. Além disso, executamos a soluc ¸ão heurística SaFER-hcg para instâncias reais de workflows com características distintas e inviáveis para execuc ¸ão com o método exato. De forma a garantir a reprodutibilidade da abordagem proposta, o código-fonte e as configurac ¸ões de ambiente e dados de entrada se encontram disponibilizados em https://github.com/UFFeScience/Wf-Security. Os métodos heurísticos e exatos foram implementados com GCC 4.8.5 e IBM ILOG CPLEX 12.8; executados em um computador com processador Intel®i5-7300U 2.60GHz, com 16GB de RAM e SO Linux Fedora 31. Além disso, cada teste foi repetido 10 vezes (com sementes aleatórias diferentes) armazenando-se a médias dos resultados. O valor dos parâmetros de entrada α LRC = 0.5 e β = 4 foram definidos de forma empírica e as ponderac ¸ões da func ¸ão objetivo α t , α b , α s foram definidas como 0,3, 0,3 e 0,4, respectivamente, baseados na experiência em trabalhos anteriores do grupo [START_REF] Teylo | A hybrid evolutionary algorithm for task scheduling and data assignment of data-intensive scientific workflows on clouds[END_REF].

Considerando o recursos computacionais necessários para a viabilidade da soluc ¸ão, utilizamos seguintes parâmetros para execuc ¸ão dos workflows: 4 VMs com diferentes capacidade de armazenamento (80, 120, 160 e 200 GBs); slowdown (quanto menor, maior o poder de processamento) (1,53, 0,77, 0,38 e 0,19); velocidade do enlace (4, 9, 10 e 10 Mbps); e o custo, por minuto, de processamento em dólares (US$ 0,02, US$ 0,09, US$ 0,16 e US$ 0,33). Em se tratando da quantidade de buckets, definimos 2 para as instâncias sintéticas e variados números para as demais instâncias (valores apresentados a seguir). Quanto a capacidade de armazenamento, velocidade do enlace e prec ¸o cobrado por GBs de dados armazenados de cada bucket, definimos como 50 TB, 25 Mbps e US$ 0,023, respectivamente. Para as instâncias públicas de workflows tradicionais (i.e., benchmarks) foram utilizadas as seguintes: (i) Montage, que cria uma imagem em mosaico a partir de fotos astronômicas menores, (ii) Cybershake, usado para identificar terremotos na Califórnia, (iii) Inspiral, usado para identificar ondas gravitacionais, (iv) Epigenomics, para sequenciamento genômico e (v) Sipht, que busca por RNA não transcrito no NCBI. Foram determinadas as seguintes quantidades de buckets para as instâncias CyberShake 30 (o número no nome da instância define a quantidade de ativac ¸ões a serem escalonadas), CyberShake 50, CyberShake 100, Epigenomics 24, Epigenomics 46, Epigenomics 100, Inspiral 30, Inspiral 50, Inspiral 100, Montage 25, Montage 50, Montage 100, Sipht 30,Sipht 50,Sipht 100: 2,8,19,6,6,44,3,8,9,6,11,28,10, 10 e 16 , respectivamente. A Tabela 1 apresenta os valores t max , c max , a quantidade de ativac ¸ões e a quantidade de arquivos (tanto os de entrada quanto os gerados durante a execuc ¸ão do workflow) escolhidos para cada instância utilizada nos experimentos.

Criamos um script para ler os arquivos que contém as instâncias dos workflows (em formato XML) e atribuir restric ¸ões (arestas fortes e fracas) entre os arquivos automaticamente, (i.e., o grafo de conflitos). Para o presente experimento, utilizamos a seguinte heurística para criac ¸ão do grafo de conflitos: (i) arquivos de entrada de uma ativac ¸ão são penalizados (com um valor padrão de 1) se armazenados junto dos arquivos de saída desta mesma ativac ¸ão (arestas fracas), (ii) arquivos gerados por ativac ¸ões em um mesmo nível do workflow (i.e., gerados por ativac ¸ões "irmãs") não podem ser armazenados juntos (arestas fortes). No caso do Montage, esta última restric ¸ão evita tanto que arquivos cabec ¸alho e corpo sejam armazenados juntos, e que arquivos que componham partes diferentes da soluc ¸ão também sejam armazenados juntos (e.g., dados gerados por diferentes ativac ¸ões que formam um mosaico). Quanto aos requisitos definidos na Sec ¸ão 3, utilizamos valores que permitissem que todas as ativac ¸ões pudessem ser executadas em qualquer VM, pois focamos nas restric ¸ões de confidencialidade, uma vez que, requisitos como autenticac ¸ão ou criptografia são funcionalidades já estudadas em trabalhos anteriores (vide Sec ¸ão 2).

A Tabela 2 apresenta os resultados das execuc ¸ões das heurística SaFER-hcg e a soluc ¸ão exata. As colunas Instância, F. O., Makespan, Custo, Confid., Tempo representam, respectivamente, as instâncias de workflows, func ¸ão objetivo, tempo de execuc ¸ão, custo e risco de exposic ¸ão, das execuc ¸ões da heurística SaFER-hcg e do método exato. Para uma melhor interpretac ¸ão, a coluna Confid. foi normalizada pelo fator S max . Os resultados indicam que o modelo matemático foi capaz de retornar soluc ¸ões ótimas para todas as instâncias sintéticas, com excec ¸ão das instâncias Sintética 15 B e Sintética 15 C que interromperam sua execuc ¸ão após uma hora (tempo limite configurado para a execuc ¸ão do CPLEX). Por outro lado, a SaFER-hcg conseguiu, para as mesmas instâncias, produzir boas soluc ¸ões com diferenc ¸a de, em média, 14% em relac ¸ão a soluc ¸ão encontrada pelo método exato, mas não conseguiu encontrar a soluc ¸ão ideal para 6 das instâncias sintéticas. Uma explicac ¸ão para a diferenc ¸a entre o método exato e a SaFER-hcg é que o método exato permite que as leituras de todas as ativac ¸ões iniciais ocorram antes de qualquer execuc ¸ão, enquanto que a heurística SaFER-hcg agrega leitura, execuc ¸ão e escrita atomicamente; isso faz com que o recurso que contém os arquivos de entrada tenha que ser alocado por mais tempo. É interessante notar que os tempos de execuc ¸ão para a SaFER-hcg são inferiores aos executados pelo CPLEX (em torno de um centésimo de segundo).

Considerando que quanto menor os valores de Confid. menor o risco de exposic ¸ão de dados confidenciais, os valores baixos demonstram a eficiência da abordagem proposta. Por último, somente a heurística SaFER-hcg conseguiu encontrar soluc ¸ões para as instâncias maiores em tempo hábil, comprovando, assim, sua importância. * A execuc ¸ão foi interrompida após uma hora de processamento.

Conclusões e Trabalhos Futuros

Diversos experimentos são modelados como workflows. Esses workflows são, geralmente, compostos por programas caixa preta com dependência de dados entre eles. Muitos dados são produzidos durante a execuc ¸ão de workflows de larga-escala. Quando essa execuc ¸ão é feita na nuvem, comumente os SGWfs existentes armazenam os dados produzidos em um storage compartilhado (i.e., bucket). Ao fazer isso, a confidencialidade do experimento pode ser comprometida. Caso um usuário malicioso venha a acessar esses arquivos, existe o risco do mesmo inferir os resultados e/ou a estrutura do experimento. Esse risco deve ser evitado, ou, pelo menos, minimizado. Nesse artigo, formalizamos o problema de escalonamento de ativac ¸ões de workflows com restric ¸ão de confidencialidade, modelando como um problema de otimizac ¸ão combinatória para preservar a confidencialidade dos dados produzidos e armazenados na nuvem. Introduzimos uma formulac ¸ão matemática e um procedimento heurístico chamado SaFER-hcg para resolver o problema de otimizac ¸ão. A abordagem proposta utiliza um grafo de conflitos para integrar o escalonamento de ativac ¸ões com o plano de dispersão dos dados determinando as áreas de armazenamento para os arquivos produzidos durante a execuc ¸ão, respeitando os limites de capacidade. A abordagem proposta foi avaliada com uma série de instâncias de workflows sintéticos e reais, e se mostrou promissora no que tange a garantia da confidencialidade ao mesmo tempo em que foi capaz de minimizar o makespan. Como trabalho futuro, pretendemos implementar uma metaheurística (e.g., GRASP) a fim de melhorar a qualidade da soluc ¸ão heurística proposta, além de implementar o SaFER-hcg no SGWf SciCumulus.

Figura 1 .

 1 Figura 1. Montage (esquerda) e exemplo de grafo de conflitos do Montage (direita).

  Tabela 3 descreve o conjunto de variáveis binárias e contínuas do modelo descrito a seguir: Indica se a ativac ¸ão i ∈ N comec ¸a sua execuc ¸ão na VM j ∈ M no período t ∈ T , ou não.-→ x idjpt Indica se a ativac ¸ão i ∈ N executando na VM j ∈ M comec ¸a a ler o dado d ∈ ∆ in (i) armazenado no recurso p ∈ M no período t ∈ T , ou não. ←x idjpt Indica se a ativac ¸ão i ∈ N executando na VM j ∈ M comec ¸a a escrita do dado d ∈ ∆ out (i) no recurso p ∈ M no período t ∈ T , ou não. y djt Indica se o dado d ∈ D está armazenado no recurso j ∈ M no período t ∈ T , ou não. y

	Var.	Descric ¸ão das variáveis binárias
	x ijt
	Var.	Descric ¸ão das varíaveis contínuas
	e ri

dj Indica se o dado d ∈ D está armazenado no recurso j ∈ M em algum momento. w d 1 d 2 Indica se os dados d 1 e d 2 estão armazenados no mesmo local ou não, onde (d 1 , d 2 ) ∈ Es. b jl Indica se o bucket j ∈ B está sendo usado no intervalo l ∈ L j , ou não. v jt Indica se a VM j ∈ M está contratada no período t ∈ T , ou não.

S Tabela 1. Detalhes das inst âncias utilizadas nos testes experimentais

	Instância	#Ativac ¸ões #Arquivos t max c max	Instância	#Ativac ¸ões #Arquivos t max	c max
	Sintética 5 A	2	3	32 120	Epigenomics 24	24	38 5.000	1.500
	Sintética 5 B	2	3	32 120	Epigenomics 46	46	71 10.000	3.000
	Sintética 5 C	1	4	40	80	Epigenomics 100	100	152 50.000 30.000
	Sintética 10 A	4	6	50 168	Inspiral 30	30	47 1.500	1.000
	Sintética 10 B	3	7	36 198	Inspiral 50	50	77 2.000	1.500
	Sintética 10 C	4	6	60 440	Inspiral 100	100	151	3.000	2.000
	Sintética 15 A	5	10	40 154	Montage 25	25	54	250	125
	Sintética 15 B	5	10	30	54	Montage 50	50	107	500	250
	Sintética 15 C	5	10	40 136	Montage 100	100	215 1.000	500
	CyberShake 30	30	49 400 200	Sipht 30	29	963 3.500 2.000
	CyberShake 50	50	79 500 250	Sipht 60	58	1.100 4.000 2.500
	CyberShake 100	100	154 600 300	Sipht 100	97	1.223 6.000 3.500

Tabela 2. Avaliac ¸ão Experimental -SaFER-hcg versus Soluc ¸ão Exata

			Heurística (SaFER-hcg)			Soluc ¸ão Exata
	Instância	F. O. Makespan (s) Custo (US$) Confid. Tempo (s)	F. O. Makespan (s) Custo (US$) Confid. Tempo (s)
	Sintética 5 A	0,25	24,00	8,32	0,00	0,01	0,25	24,00	8,32	0,00	0,16
	Sintética 5 B	0,28	27,00	9,35	0,00	0,01	0,28	27,00	9,21	0,00	1,29
	Sintética 5 C	0,32	36,00	12,12	0,00	0,01	0,32	36,00	12,12	0,00	0,21
	Sintética 10 A	0,33	48,00	22,42	0,00	0,01	0,24	35,00	16,81	0,00	1.039,48
	Sintética 10 B	0,28	31,00	14,24	0,00	0,01	0,26	29,00	11,68	0,00	60,68
	Sintética 10 C	0,31	58,00	24,78	0,00	0,01	0,28	53,00	22,97	0,00	18,44
	Sintética 15 A	0,15	19,00	4,90	0,00	0,01	0,11	14,00	4,59	0,00	285,60
	Sintética 15 B	0,29	20,00	11,60	0,07	0,01	0,24	16,00	8,88	0,07 3.740,48 *
	Sintética 15 C	0,34	36,80	17,81	0,05	0,01	0,29	29,00	16,63	0,09 3.604,57 *
	CyberShake 30	0,27	158,30	93,02	0,02	0,19
	CyberShake 50	0,39	294,20	172,95	0,01	0,78
	CyberShake 100	0,46	420,40	249,78	0,01	7,15
	Epigenomics 24	0,42	2.698,50	1.204,41	0,04	0,12
	Epigenomics 46	0,43	4.928,40	2.773,21	0,02	0,40
	Epigenomics 100	0,53	43.722,10	26.285,44	0,02	7,24
	Montage 25	0,34	857,90	522,29	0,02	0,11
	Montage 50	0,42	1.532,50	944,01	0,01	0,41
	Montage 100	0,49	2.509,20	1.566,27	0,00	2,25
	Inspiral 30	0,33	130,30	68,70	0,02	0,15
	Inspiral 50	0,35	266,60	155,43	0,01	1,59
	Inspiral 100	0,37	561,90	329,79	0,00	19,13
	Sipht 30	0,49	2.869,70	1.440,52	0,06	3,26
	Sipht 60	0,55	3.664,10	2.105,33	0,06	17,16
	Sipht 100	0,46	4.622,00	2.571,43	0,03	52,63