Algorithmic diversity through semantic program comparison
La diversidad es una propiedad bien estudiada en el diseño de software, especialmente en áreas como la seguridad o los sistemas distribuidos. Sin embargo, a la hora de diseñar un sistema, no existen formas adecuadas de medir la diversidad real entre las distintas implementaciones del mismo. Por tant...
- Autores:
-
Trujillo Achury, Miller Andrés
- Tipo de recurso:
- Fecha de publicación:
- 2021
- Institución:
- Universidad de los Andes
- Repositorio:
- Séneca: repositorio Uniandes
- Idioma:
- eng
- OAI Identifier:
- oai:repositorio.uniandes.edu.co:1992/55118
- Acceso en línea:
- http://hdl.handle.net/1992/55118
- Palabra clave:
- Semantic equivalence
Program similitude
Code clones
Algorithmic diversity
Ingeniería
- Rights
- openAccess
- License
- http://creativecommons.org/licenses/by-nc-nd/4.0/
| id |
UNIANDES2_a32e0c344d40562396700033101a8ac9 |
|---|---|
| oai_identifier_str |
oai:repositorio.uniandes.edu.co:1992/55118 |
| network_acronym_str |
UNIANDES2 |
| network_name_str |
Séneca: repositorio Uniandes |
| repository_id_str |
|
| dc.title.eng.fl_str_mv |
Algorithmic diversity through semantic program comparison |
| title |
Algorithmic diversity through semantic program comparison |
| spellingShingle |
Algorithmic diversity through semantic program comparison Semantic equivalence Program similitude Code clones Algorithmic diversity Ingeniería |
| title_short |
Algorithmic diversity through semantic program comparison |
| title_full |
Algorithmic diversity through semantic program comparison |
| title_fullStr |
Algorithmic diversity through semantic program comparison |
| title_full_unstemmed |
Algorithmic diversity through semantic program comparison |
| title_sort |
Algorithmic diversity through semantic program comparison |
| dc.creator.fl_str_mv |
Trujillo Achury, Miller Andrés |
| dc.contributor.advisor.none.fl_str_mv |
Cardozo Álvarez, Nicolás |
| dc.contributor.author.spa.fl_str_mv |
Trujillo Achury, Miller Andrés |
| dc.contributor.jury.spa.fl_str_mv |
Takahashi Rodríguez, Silvia Nallur, Vivek |
| dc.subject.keyword.none.fl_str_mv |
Semantic equivalence Program similitude Code clones Algorithmic diversity |
| topic |
Semantic equivalence Program similitude Code clones Algorithmic diversity Ingeniería |
| dc.subject.themes.none.fl_str_mv |
Ingeniería |
| description |
La diversidad es una propiedad bien estudiada en el diseño de software, especialmente en áreas como la seguridad o los sistemas distribuidos. Sin embargo, a la hora de diseñar un sistema, no existen formas adecuadas de medir la diversidad real entre las distintas implementaciones del mismo. Por tanto, proponemos una nueva métrica de diversidad basada en técnicas de análisis de similitud de programas que utiliza la representación de grafos de flujo de control para determinar el grado de similitud de dos programas dados. Dividimos nuestro trabajo en dos partes principales: El análisis de la similitud de los programas y el análisis del impacto de la diversidad en el software. Para validar nuestro enfoque de análisis de la similitud de los programas, utilizamos programas simples de los dominios de los algoritmos de ordenamiento, búsqueda y agregación, midiendo la similitud entre las diferentes implementaciones. Además, utilizamos un nuevo corpus creado a partir de problemas de concursos virtuales de programación competitiva para descubrir la similitud entre las soluciones presentadas por los concursantes. Para evaluar el impacto de la diversidad, utilizamos una configuración de balanceadores de carga que implementan diferentes algoritmos, y medimos el rendimiento del sistema utilizando la latencia y la tasa de errores. Nuestros resultados muestran que, de hecho, nuestro enfoque para analizar la similitud de los programas detecta correctamente la similitud entre diferentes implementaciones de programas, y marca como diferentes aquellas implementaciones a problemas no relacionados, con un rendimiento comparable a los enfoques existentes. Por último, también observamos que al añadir diversidad a la configuración de balanceadores de carga se reducía la latencia de todo el sistema, sin impactar las tasas de error. |
| publishDate |
2021 |
| dc.date.issued.none.fl_str_mv |
2021 |
| dc.date.accessioned.none.fl_str_mv |
2022-02-22T19:50:51Z |
| dc.date.available.none.fl_str_mv |
2022-02-22T19:50:51Z |
| dc.type.spa.fl_str_mv |
Trabajo de grado - Maestría |
| dc.type.driver.spa.fl_str_mv |
info:eu-repo/semantics/masterThesis |
| dc.type.version.spa.fl_str_mv |
info:eu-repo/semantics/acceptedVersion |
| dc.type.content.spa.fl_str_mv |
Text |
| dc.type.redcol.spa.fl_str_mv |
http://purl.org/redcol/resource_type/TM |
| status_str |
acceptedVersion |
| dc.identifier.uri.none.fl_str_mv |
http://hdl.handle.net/1992/55118 |
| dc.identifier.pdf.spa.fl_str_mv |
25477.pdf |
| dc.identifier.instname.spa.fl_str_mv |
instname:Universidad de los Andes |
| dc.identifier.reponame.spa.fl_str_mv |
reponame:Repositorio Institucional Séneca |
| dc.identifier.repourl.spa.fl_str_mv |
repourl:https://repositorio.uniandes.edu.co/ |
| url |
http://hdl.handle.net/1992/55118 |
| identifier_str_mv |
25477.pdf instname:Universidad de los Andes reponame:Repositorio Institucional Séneca repourl:https://repositorio.uniandes.edu.co/ |
| dc.language.iso.spa.fl_str_mv |
eng |
| language |
eng |
| dc.rights.uri.*.fl_str_mv |
http://creativecommons.org/licenses/by-nc-nd/4.0/ |
| dc.rights.accessrights.spa.fl_str_mv |
info:eu-repo/semantics/openAccess |
| dc.rights.coar.spa.fl_str_mv |
http://purl.org/coar/access_right/c_abf2 |
| rights_invalid_str_mv |
http://creativecommons.org/licenses/by-nc-nd/4.0/ http://purl.org/coar/access_right/c_abf2 |
| eu_rights_str_mv |
openAccess |
| dc.format.extent.spa.fl_str_mv |
16 páginas |
| dc.format.mimetype.spa.fl_str_mv |
application/pdf |
| dc.publisher.spa.fl_str_mv |
Universidad de los Andes |
| dc.publisher.program.spa.fl_str_mv |
Maestría en Ingeniería de Sistemas y Computación |
| dc.publisher.faculty.spa.fl_str_mv |
Facultad de Ingeniería |
| dc.publisher.department.spa.fl_str_mv |
Departamento de Ingeniería de Sistemas y Computación |
| institution |
Universidad de los Andes |
| bitstream.url.fl_str_mv |
https://repositorio.uniandes.edu.co/bitstreams/6ad19934-16fe-40c7-b988-ef7aef58adae/download https://repositorio.uniandes.edu.co/bitstreams/e254b487-9c6e-400d-985f-ec8bd440b3af/download https://repositorio.uniandes.edu.co/bitstreams/9ad89558-e678-46cc-a033-1038a67d056c/download |
| bitstream.checksum.fl_str_mv |
f0c2e398ce5417a693333f764c4ce65b 1a3d9fb06d8b8d38be7c9ee56df1e009 42879d0b0b1e83d32f5fad73971529f9 |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 MD5 MD5 |
| repository.name.fl_str_mv |
Repositorio institucional Séneca |
| repository.mail.fl_str_mv |
adminrepositorio@uniandes.edu.co |
| _version_ |
1812133847811227648 |
| spelling |
Al consultar y hacer uso de este recurso, está aceptando las condiciones de uso establecidas por los autores.http://creativecommons.org/licenses/by-nc-nd/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Cardozo Álvarez, Nicolásvirtual::3382-1Trujillo Achury, Miller Andrés076fbd43-d65d-485a-8a33-f919bb834251400Takahashi Rodríguez, SilviaNallur, Vivek2022-02-22T19:50:51Z2022-02-22T19:50:51Z2021http://hdl.handle.net/1992/5511825477.pdfinstname:Universidad de los Andesreponame:Repositorio Institucional Sénecarepourl:https://repositorio.uniandes.edu.co/La diversidad es una propiedad bien estudiada en el diseño de software, especialmente en áreas como la seguridad o los sistemas distribuidos. Sin embargo, a la hora de diseñar un sistema, no existen formas adecuadas de medir la diversidad real entre las distintas implementaciones del mismo. Por tanto, proponemos una nueva métrica de diversidad basada en técnicas de análisis de similitud de programas que utiliza la representación de grafos de flujo de control para determinar el grado de similitud de dos programas dados. Dividimos nuestro trabajo en dos partes principales: El análisis de la similitud de los programas y el análisis del impacto de la diversidad en el software. Para validar nuestro enfoque de análisis de la similitud de los programas, utilizamos programas simples de los dominios de los algoritmos de ordenamiento, búsqueda y agregación, midiendo la similitud entre las diferentes implementaciones. Además, utilizamos un nuevo corpus creado a partir de problemas de concursos virtuales de programación competitiva para descubrir la similitud entre las soluciones presentadas por los concursantes. Para evaluar el impacto de la diversidad, utilizamos una configuración de balanceadores de carga que implementan diferentes algoritmos, y medimos el rendimiento del sistema utilizando la latencia y la tasa de errores. Nuestros resultados muestran que, de hecho, nuestro enfoque para analizar la similitud de los programas detecta correctamente la similitud entre diferentes implementaciones de programas, y marca como diferentes aquellas implementaciones a problemas no relacionados, con un rendimiento comparable a los enfoques existentes. Por último, también observamos que al añadir diversidad a la configuración de balanceadores de carga se reducía la latencia de todo el sistema, sin impactar las tasas de error.Diversity is a well-studied property of software design, specially in areas like security or distributed systems. However, when designing a system, there are no proper ways for measuring actual diversity between different implementations within it. We proposed a novel diversity metric based on an improved program similitude technique that uses the control flow graph representation of programs to determine how similar are two given programs. We divided our work into two main parts: Analyzing program similitude, and analyzing the impact of diversity in software. To validate our approach for analyzing program similitude, we used simple programs from the domains of sorting, search and aggregation algorithms, measuring the similitude between the different implementations. Additionally, we use a new corpus created from competitive programming virtual judges problems to discover similitude between solutions submitted by contestants. To evaluate the impact of diversity, we used a setup of load balancers which implements different algorithms, and measured system performance using latency and error rate. Our results show that in fact, our approach for analyzing program similitude correctly detects similitude between different program implementations, and marks as different those implementations to unrelated programs problems, with a performance comparable to existing approaches. Finally, we also observed that adding diversity to the setup of load balancers reduced the latency of the whole systems, however we did not find any improvement on the error rates. Additionally, we noted a logarithmic proportionality between the number of algorithms and the diversity value calculated with our approach. This exhibits that increasing the number of algorithms will increase diversity, but after a certain limit we do not expect the diversity to change significantly, and neither systems' performance.Magíster en Ingeniería de Sistemas y ComputaciónMaestría16 páginasapplication/pdfengUniversidad de los AndesMaestría en Ingeniería de Sistemas y ComputaciónFacultad de IngenieríaDepartamento de Ingeniería de Sistemas y ComputaciónAlgorithmic diversity through semantic program comparisonTrabajo de grado - Maestríainfo:eu-repo/semantics/masterThesisinfo:eu-repo/semantics/acceptedVersionTexthttp://purl.org/redcol/resource_type/TMSemantic equivalenceProgram similitudeCode clonesAlgorithmic diversityIngeniería201517402Publicationhttps://scholar.google.es/citations?user=3iTzjQsAAAAJvirtual::3382-10000-0002-1094-9952virtual::3382-1a77ff528-fc33-44d6-9022-814f81ef407avirtual::3382-1a77ff528-fc33-44d6-9022-814f81ef407avirtual::3382-1TEXT25477.pdf.txt25477.pdf.txtExtracted texttext/plain65173https://repositorio.uniandes.edu.co/bitstreams/6ad19934-16fe-40c7-b988-ef7aef58adae/downloadf0c2e398ce5417a693333f764c4ce65bMD52ORIGINAL25477.pdfapplication/pdf823910https://repositorio.uniandes.edu.co/bitstreams/e254b487-9c6e-400d-985f-ec8bd440b3af/download1a3d9fb06d8b8d38be7c9ee56df1e009MD51THUMBNAIL25477.pdf.jpg25477.pdf.jpgIM Thumbnailimage/jpeg30011https://repositorio.uniandes.edu.co/bitstreams/9ad89558-e678-46cc-a033-1038a67d056c/download42879d0b0b1e83d32f5fad73971529f9MD531992/55118oai:repositorio.uniandes.edu.co:1992/551182024-03-13 12:25:26.368http://creativecommons.org/licenses/by-nc-nd/4.0/open.accesshttps://repositorio.uniandes.edu.coRepositorio institucional Sénecaadminrepositorio@uniandes.edu.co |